SGLang/RadixAttention

RadixAttention：共享请求前缀

用压缩前缀树组织 token 序列，让多轮对话和分支生成共享已有 KV。

70528762bf0800793dab10d1b51d40f21a0608ba · 2024-01-17缓存与复用核验 2026-10-08

工程问题#

多个生成调用存在共同前文，但调用结束后直接释放缓存会丢失跨请求复用机会。

实际实现#

原始 RadixAttention 在 CPU 保存 radix tree，边表示 token 片段，节点关联 GPU 上的 KV；容量不足时按 LRU 从可淘汰叶节点回收。

处理流程#

在树中匹配最长已缓存前缀
复用对应 KV 并计算未命中部分
必要时拆分压缩边并插入新分支
内存紧张时递归淘汰叶节点

源码片段#

固定版本 · 原文摘录

python/sglang/srt/managers/router/radix_cache.py70528762bf0800793dab10d1b51d40f21a0608ba · 2024-01-17 · L113–L127

查看原文件

113    def _match_prefix_helper(self, node, key, value, last_node):114        node.last_access_time = time.time()115116        for c_key, child in node.children.items():117            prefix_len = match(c_key, key)118            if prefix_len != 0:119                if prefix_len < len(c_key):120                    new_node = self._split_node(c_key, child, prefix_len)121                    value.append(new_node.value)122                    last_node[0] = new_node123                else:124                    value.append(child.value)125                    last_node[0] = child126                    self._match_prefix_helper(child, key[prefix_len:], value, last_node)127                break

RadixCache._match_prefix_helper

比较压缩边的 token 前缀：部分匹配则拆边形成新节点，完整匹配则收集缓存位置并递归处理剩余 token，同时更新时间。value 组织的是复用信息，这段不会重新执行 Attention；淘汰和引用保护由同文件其他方法处理。此早期实现逐个检查子边，不能据此给出与分支数量无关的严格 O(L) 保证。

PYTHONApache-2.0

固定为原始设计文章同日的仓库 commit；源码路径与后续 SGLang 版本不同，不代表最新缓存后端。

收益与取舍#

工程分析

带来的收益

自动发现不同调用的公共前缀
树形分支表达共享与分歧位置

付出的代价

节点拆分和淘汰带来维护成本
收益取决于前缀重复率与可用缓存容量

可比较的选择

块哈希索引固定块键便于映射查询；树则直接表达变长前缀分支。

版本与适用范围#

历史设计基线；原文描述 CPU 树与 GPU KV 分离。后续多层缓存、分页粒度和调度演进需另建版本案例。

参考来源#

源码、官方文档与原始论文

SGLang 原始 RadixAttention 设计

Backend: RadixAttention · RadixAttention / LRU leaf eviction

官方文档2024-01-17 原始设计