RadixAttention

# RadixAttention 深度解析 RadixAttention 完整指南 - SGLang 用于自动前缀缓存的核心创新。 ## 什么是 RadixAttention？ **RadixAttention** 是一种通过基数树 (radix tree) 数据结构，自动缓存并重用跨请求公共前缀的 KV 缓存的算法。 **核心洞察**：在实际的 LLM 服务中： - 系统提示词在请求间重复 - 少样本 (Few-shot) 示例是共享的 - 多轮对话基于之前的上下文构建 - 智能体工具/函数定义是一次性的 **传统服务的痛点**： - 每个请求都重新计算整个提示词 - 对共享前缀造成浪费 - 比必要速度慢 5-10 倍 **RadixAttention 解决方案**： - 构建所有已处理 Token 的基数树 - 自动检测共享前缀 - 重用匹配 Token 的 KV 缓存 - 仅计算新的/不同的 Token ## 工作原理 ### 基数树结构 示例请求: 1. "System: You are helpfulnUser: What's AI?" 2. "System: You are helpfulnUser: What's ML?" 3. "System: You are helpfulnUser: What's DL?" 基数树: Root └── "System: You are helpfulnUser: What's " ├── "AI?" → [请求 1 的 KV 缓存] ├── "ML?" → [请求 2 的 KV 缓存] └── "DL?" → [请求 3 的 KV 缓存] 共享前缀: "System: You are helpfulnUser: What's " → 计算一次，重用 3 次 → 5 倍加速! ### Token 级匹配 RadixAttention 在 Token 级别工作： python # 请求 1: "Hello world" Tokens: [15496, 1917] # Hello=15496, world=1917 → KV 缓存已计算并存储在树中 # 请求 2: "Hello there" Tokens: [15496, 612] # Hello=15496, there=612 → 重用 Token 15496 的 KV 缓存 → 仅计算 Token 612 → 2 倍加速 ### 自动驱逐 当内存已满时： 1. **LRU 策略**: 驱逐最近最少使用的前缀 2. **叶子优先**: 在内部节点之前移除叶子节点 3. **保留公共前缀**: 频繁使用的前缀保持缓存状态 驱逐前 (内存已满): Root ├── "System A" (5 分钟前使用) │ ├── "Task 1" (1 分钟前使用) ← 保留 (最近) │ └── "Task 2" (30 分钟前使用) ← 驱逐 (旧 + 叶子) └── "System B" (60 分钟前使用) ← 驱逐 (非常旧) 驱逐后: Root └── "System A" └── "Task 1" ## 性能分析 ### 少样本提示 (Few-Shot Prompting) **场景**: 提示词中有 10 个示例 (2000 个 Token)，用户查询 (50 个 Token) **不使用 RadixAttention** (vLLM): - 请求 1: 计算 2050 个 Token (2000 个示例 + 50 个查询) - 请求 2: 计算 2050 个 Token (重新计算所有示例) - 请求 3: