RadixAttention 深潜：一棵树如何吃掉 5 倍吞吐

前情说明：上一篇《vLLM vs SGLang 的架构哲学》把两个引擎的宏观分歧讲完了。这一篇专门深潜 SGLang 最核心的贡献——RadixAttention——从数据结构、算法、eviction 策略、并发处理一路挖到底。 素材来自 LMSYS 官方博客 2024-01-17 那篇发布公告 + SGLang 论文（arxiv 2312.07104）。

---

起手：一个尴尬的事实

2024 年初，SGLang 在 A10G GPU 上跑 Llama-7B，在 tree-of-thought、self-consistency、多轮 chat 这些 workload 上，吞吐比 vLLM 高 5 倍。

不是 50%，是 5 倍。

这个数字第一眼看起来夸张到不真实——vLLM 已经是当时的 SOTA 了。为什么会有 5x 差距？

答案不是某个 kernel 优化、不是新的 CUDA 技巧，而是一个数据结构的选择：把 KV cache 从"每 request 独立分页"改成"全局共享的 radix tree"。

5x 吞吐的秘密，在一棵树里。这篇文章就把这棵树彻底挖开。

---

一、问题域：LLM workload 里的重复计算

先看四个真实场景（图片可以脑补）：

场景 1: Few-shot 学习
┌────────────────────────────────────┐
│ 示例1: Q: 1+1=? A: 2               │
│ 示例2: Q: 2+2=? A: 4               │ ← 共享前缀
│ 示例3: Q: 3+3=? A: 6               │
├────────────────────────────────────┤
│ 请求 1: Q: 5+5=? A: ?              │
│ 请求 2: Q: 7+7=? A: ?              │
│ 请求 3: Q: 9+9=? A: ?              │
└────────────────────────────────────┘

场景 2: Self-Consistency
Q: "求解数学题 X"
├── 采样 1: "让我用方法 A..."
├── 采样 2: "让我用方法 B..."
├── 采样 3: "让我用方法 C..."
...
├── 采样 10: "让我用方法 J..."
    ↑ 都从同一个 Q 出发

场景 3: 多轮 Chat
第 1 轮: [system, user_1, assistant_1]
第 2 轮: [system, user_1, assistant_1, user_2, assistant_2]  ← 前缀是第 1 轮
第 3 轮: [system, ..., user_3, assistant_3]                   ← 前缀是第 2 轮

场景 4: Tree-of-Thought
                Root Problem
             /       |         \
        Thought A  Thought B  Thought C     ← 共享 root
        /    \                     |
    A1      A2                    C1        ← A1 A2 共享 A

共同特征：这些 workload 里，多个 request 之间存在结构化的公共前缀。传统推理引擎（尤其是 vLLM v0 时代）不能自动发现这些前缀，每个 request 独立算——大量重复计算和显存浪费。

要解决这个问题，需要一个数据结构能同时做三件事：

1. 高效查前缀（新请求进来，找最长匹配）
2. 高效插入新序列（生成完的 token 立刻能被后续请求复用）
3. 高效淘汰（显存不够时，能识别哪些前缀最不常用）

radix tree 是这三个需求的完美答案。

---

二、Radix Tree：为什么不是 Trie

在算法课上大家都学过 trie（前缀树）：每条边一个字符，共享前缀能自然合并。

那为什么 SGLang 不直接用 trie？看下面这两棵树存 ["hello", "help", "helm"]：

Trie:                        Radix Tree:
      root                        root
       │                            │
       h                          "he"
       │                          / | \
       e                         "llo" "lp" "lm"
       │
       l
      /|\
    l  p m
    │
    o

Radix tree 允许一条边存一个字符串（不是单字符）。这带来两个关键好处：

1. 深度大幅降低——找一个前缀路径不用穿透太多节点
2. 每个节点存的信息更多——一条边存一整段 token 序列 → 每条边对应一批 KV cache block

对 LLM 场景至关重要——一个 system prompt 可能有几百 token，如果用 trie 就是几百层深度，性能爆炸。用 radix tree，一条边直接搞定。

---

三、RadixAttention 的核心结构

SGLang 的 RadixAttention 建立了这样一个映射：

Key:   token 序列 (variable length)
Value: 对应的 KV cache tensor block 列表

用一张图看：

                    Root
                     │
                edge = "You are a helpful assistant"
                (KV blocks: [b0, b1, b2, b3])
                     │
              ┌──────┴──────┐
              │             │
       edge = "\n\nUser:  edge = "\n\nUser:
       hello.\n\nAssistant:  what is AI?\n\nAssistant:
       hi."                  AI is..."
       (KV blocks:           (KV blocks:
       [b4, b5])              [b6, b7, b8])
              │
       edge = "\n\nUser:
       how are you?"
       (KV blocks: [b9])

关键性质：

• 树结构存 CPU 端（tree 本身开销很小）
• KV cache tensor 存 GPU HBM（paged 布局，page size = 1 token）
• 多个 request 可以在树的不同分支上共享祖先节点的 KV

3.1 一次请求进来发生什么？

假设有个新请求 "You are a helpful assistant\n\nUser: how are you?\n\nAssistant:"：

1. 前缀匹配：从 root 开始 walk tree，找最长匹配路径
   • 走到 "You are a helpful assistant" → 匹配
   • 走到 "\n\nUser: hello.\n\nAssistant: hi." → 匹配
   • 走到 "\n\nUser: how are you?" → 匹配
2. 复用：匹配到的这几段 KV block 直接用（reference count +1）
3. 新增：只对剩下不匹配的 token（这里是 \n\nAssistant:）跑 prefill
4. 插入：生成完 assistant reply 之后，作为新节点插入树

收益：本来要跑几百 token 的 prefill，现在只跑最后几十个。prefill 加速 5-10 倍是常态。

---

四、九步操作示例：树是怎么动态变化的

这是 SGLang 博客里最精彩的一张图。九步展示 radix tree 在真实 workload 下的演化：

Step 1：树为空。

Step 2：处理 chat session 1 第一轮："You are a helpful assistant. User: Hello. Assistant: Hi"

• 全部作为一条边加入根节点
• 树里现在有一个节点 b

Step 3：chat session 1 第二轮："...User: Hello. Assistant: Hi. User: How are you?"

• 前缀匹配到 b
• 把新增部分作为 b 的子节点插入
• 树: root → b → c

Step 4：chat session 2 开始："You are a helpful assistant. User: What is AI?"

• 匹配到 b 的前半段 "You are a helpful assistant"
• 节点 b 被 split——前半段变共享父节点，原后半段作为一个子节点，新的作为另一个子节点
• 树: root → b(split) → { b_rest → c, d }

Step 5：chat session 2 继续。

• 显存不够，b_rest → c 分支（chat 1 的历史）被 evict
• 新对话继续从 d 之后接

Step 6：新的 few-shot 查询进来（跟已有节点无共享前缀）

• root 被 split，few-shot 查询作为新分支 e 挂在 root 下

Step 7：一批 few-shot 查询（共享 few-shot examples）

• Split e，让共享部分作为父节点，各自的 query 作为子节点

Step 8：chat 1 又发消息进来

• 但显存不够，LRU 把 chat 2 相关的节点全部 evict（g 和 h）
• chat 1 复用之前 evict 掉的路径需要重新算——但只算 evict 掉那部分

Step 9：一个 self-consistency 请求进来（对 j 采样多个答案）

• 需要空间——evict 掉 few-shot 相关的 i, k, l

这九步覆盖了 RadixAttention 会遇到的所有基础操作：insert、split、reuse、evict、reference count。

---

五、算法细节

5.1 前缀匹配

find_longest_prefix(tokens):
    node = root
    matched = []
    while node has children:
        for child in node.children:
            common = longest_common_prefix(tokens[matched.len:], child.edge)
            if common == child.edge:
                # 完整匹配这条边，继续深入
                matched.append(child)
                node = child
                break
            elif common.length > 0:
                # 部分匹配 → split
                split_node(child, common.length)
                matched.append(new_split_child)
                return matched
        else:
            break  # 没有 child 匹配
    return matched

关键点：部分匹配触发 split——把边切开，让共享部分成为父节点。这是 radix tree 保持"每个节点代表一个独特分叉"的关键。

5.2 Split 操作

一条边 "You are a helpful assistant. User: Hello" 如果新请求只匹配到 "You are a helpful assistant." 就要 split：

Before:
    root
     │
    "You are a helpful assistant. User: Hello"  → KV blocks [b0-b7]

After split:
    root
     │
    "You are a helpful assistant."  → KV blocks [b0-b3]
     │
    ". User: Hello"                 → KV blocks [b4-b7]

注意：KV block 也要切——因为 block 是 paged 布局，切开是 O(1) 的（只是改指针）。

5.3 LRU Eviction

显存有上限。当 free block pool 不够用时，触发 LRU eviction：

evict_until_enough_space(required_blocks):
    while free_pool.size < required_blocks:
        # 找 LRU 的叶子节点
        victim_leaf = find_lru_leaf()
        # 释放它的 KV blocks 回 free_pool
        for block in victim_leaf.kv_blocks:
            free_pool.push(block)
        # 从树里删掉
        remove_node(victim_leaf)
        # 如果父节点变成叶子且没在被引用，也可以继续 evict

为什么只 evict 叶子？ 因为内部节点被 evict 的话，它的 KV 是当前活跃 request 依赖的——不能 evict。只有叶子（没被任何 request 引用的路径末端）才能安全释放。

递归 evict 直到父节点也变叶子——这是关键。否则一次 evict 只能回收几个 block，效率太低。

5.4 Reference Counting

每个 tree 节点带 reference count：

• Request 使用这个节点的 KV 时 refcount +1
• Request 完成时 refcount -1
• refcount > 0 的节点不能 evict

这保证了正在跑的 request 不会被抽走 KV——即使它对应的路径很旧、很久没用。

---

六、Cache-Aware Scheduling：把请求编排成"友好顺序"

RadixAttention 只是数据结构。Scheduler 也要跟着优化——决定请求跑的顺序，让缓存命中率最大化。

SGLang 的调度策略叫 cache-aware scheduling：

朴素 FCFS 调度:
    request_1 (share prefix A) → 加载 A → 算
    request_2 (share prefix B) → 加载 B → 算 (evict A)
    request_3 (share prefix A) → 加载 A → 算 (evict B)
    ↑ A 被反复加载

Cache-aware 会把共享前缀的 request 尽量安排在一起：

Cache-aware 调度:
    request_1 (prefix A) → 加载 A → 算
    request_3 (prefix A) → 直接复用 A → 算  ← 命中
    request_2 (prefix B) → evict A → 加载 B → 算

思想：在时间维度上聚集同前缀 request，让 KV 只需加载一次。

这个策略的收益跟 workload 强相关：agent workload、few-shot batch 上收益特别大（缓存命中率能到 75%+），随机 workload 上收益小（但也没损失）。

Ablation study：即使没有缓存命中，RadixAttention 也没有可测量的额外 overhead——所以 SGLang 默认永远开着。

---

七、和 vLLM Prefix Caching 的对比

到 2026 年，vLLM 也有 prefix caching 了。表面看功能一样，但底层实现有本质差异：

维度	vLLM Prefix Caching	SGLang RadixAttention
数据结构	Hash map (BlockHash → Block)	Radix Tree
共享单元	Fixed-size block (16 tokens)	Variable-length edge
查找方式	按 block 逐个 hash 匹配	树 walk + 边内部 longest common prefix
对齐要求	前缀必须对齐 16 token 边界	可以匹配任意长度
Split 操作	❌ 不需要（block 已经是最小单元）	✅ 需要（用来切边）
淘汰策略	LRU on blocks	LRU on tree leaves
树状 workload 支持	⚠️ 有限	✅ 天然

核心差异：vLLM 的 hash 是离散的——只能匹配到 16 token 的整数倍；SGLang 的 tree 是连续的——可以匹配到任意长度。

对典型 chat 场景差异不大（system prompt 通常几百 token，远大于 16）。但对某些 workload：

• Tree-of-Thought：一个思路分叉点可能只有几个 token，vLLM 的 block 粒度会漏掉这个共享
• Beam search：beam 分叉在 token 边界，radix tree 天然支持
• Speculative sampling 验证阶段：draft 分叉更细，radix tree 更精细

这就是为什么 SGLang 在 tree-of-thought 上跑出 5x——不只是有缓存，是缓存粒度更细。

---

八、扩展话题：Multimodal 与 Approximate Radix Tree

8.1 处理多模态

RadixAttention 天然支持多模态——image token 也是 token。

多模态 prompt 长这样：

[图片 tokens (256 个)] "描述这张图"

如果多个 request 用同一张图，图片的 256 个 token 会共享。图片 hash 作为一个特殊 token embedding 插入 tree。

8.2 分布式场景：Approximate Radix Tree

SGLang v0.4 的 cache-aware router 引入了近似 radix tree——

问题：8 个 DP 副本，每个副本有自己的 radix tree。Router 想让请求路由到"缓存命中率最高"的副本。但每个副本的 tree 状态不能实时同步（同步开销太大）。

解法：Router 维护一棵近似的全局 tree——记录哪些前缀"大概率"在哪些 worker 上。用惰性更新（worker 处理完请求后异步通知 router），几乎零同步开销。

牺牲：路由决策不一定 100% 准确（近似），但胜在几乎零开销。实际效果：cache hit rate 从 20% → 75%。

---

九、未来演进：多层存储与更智能的 Eviction

SGLang 博客最后暗示了几个演进方向：

9.1 多层存储

现在的 RadixAttention 只有 GPU HBM 这一层。未来可能加：

• CPU DRAM 层（比 HBM 慢，但便宜、大）
• SSD 层（更慢，但极大——存"冷缓存"）

Evict 的时候不是丢弃，是降级——从 HBM → DRAM → SSD。命中 SSD 也比重算好。LMCache 项目就在做这个（vLLM 集成的 KV 服务），SGLang 也在跟进。

9.2 更智能的 Eviction

LRU 是最朴素的策略。未来可以基于访问频率、剩余 token 数、request 优先级做更精细的决策。这块目前学术研究还比较早期。

9.3 语义级共享

现在的共享是精确匹配——两段 token 必须完全一样。未来能不能语义层面共享？比如两个不同措辞但意思相同的 prompt 共享部分 KV？

这是研究前沿——Semantic KV Cache——初步方案是用小 embedding model 做前缀相似度匹配。目前还没进生产。

---

十、总结：一棵树的哲学胜利

RadixAttention 的技术胜利可以浓缩成三句话：

1. 数据结构决定性能上限——同样是 KV cache 复用，hash map 和 tree 的表达力差异极大。tree 天然表达"任意长度共享"，是这一切的基础。
2. 调度和数据结构必须协同设计——radix tree 单独用不够，配合 cache-aware scheduling 才能把缓存命中率推到 75%+。
3. 对 workload 结构的 assumption 决定引擎的适用面——SGLang 假设 LLM workload 是"有共享结构的程序"，这个 assumption 在 agent 时代被完美验证。

回到那个 5x 吞吐的数字——不是靠优化，是靠假设。当你的假设跟真实 workload 匹配，性能就是数量级的差距。

下次看到某个系统"性能翻倍"、"性能 10x"的时候，请先问一句：它对 workload 的 assumption 是什么？ 那才是真正的答案。

---

附：素材来源

主线

• LMSYS Blog · Fast and Expressive LLM Inference with RadixAttention and SGLang（2024-01-17）
• LMSYS Blog · SGLang v0.4（2024-12-04，cache-aware router 部分）
• SGLang Paper · Efficiently Programming Large Language Models using SGLang

相关工作

• Preble · arxiv 2407.00023（另一个基于 SGLang 的分布式 prefix cache 系统）
• LMCache · vLLM 的分层 KV cache 项目

姊妹篇

• 《vLLM vs SGLang：两个推理引擎的架构哲学》
• 《现代 LLM 推理引擎剖析》

---

整理于 2026-07-31。原文技术细节归属 SGLang / LMSYS 团队。中文表达可能有解读偏差，请以原文为准。