简报文章论文故事系列 v1 系列探索实践

32 · SGLang — RadixAttention + 结构化生成执行引擎

推理部署 SGLang 2023
Zheng et al., UC Berkeley · arXiv:2312.07104

迭代了什么

上一代的问题：PagedAttention 只能 exact match 前缀，无法部分匹配树状结构。结构化输出需事后 parse 和 retry。

这代改了什么：RadixAttention 树状 KV Cache + token 级别 FSM 结构约束 + DAG 图调度。

效果：KV Cache 减少 67%（prefix sharing），结构化零 retry，多跳链式 ~2× 加速。

一、一句话总结

通过 RadixAttention（树状 KV Cache）和 token 级别结构化输出约束，将 LLM serving 升级为可编程的执行引擎。

二、核心创新1：RadixAttention

树状 KV Cache，支持 partial match 和 fork-aware prefix sharing。以基数树（Radix Tree）结构组织所有请求的 KV Cache。

请求 A: "sys + question A" → 共享 "sys" 节点
请求 B: "sys + question B" → 共享 "sys" 节点
请求 C: "sys + question A + follow-up" → 共享 "sys + question A"

匹配到最长公共前缀的物理 block 直接复用，LRU 淘汰不常用的叶节点。

三、核心创新2：Token-Level 结构化输出

生成过程中用 FSM（Finite State Machine）实时 mask 非法 token，无需事后 parse 和 retry。

JSON Schema 编译为自动机，每步只允许符合 schema 的 token
支持正则表达式约束和上下文无关语法
解码时零额外的 LLM 调用开销

四、核心创新3：Graph-Based DAG 调度

将多跳链式调用（prompt chain）建模为 DAG，自动并行化无关节点，跨节点共享 KV Cache。

program: < prompt1 → LLM call 1 → program transform → LLM call 2 → ... >
SGLang 运行时自动识别无数据依赖的节点并行执行
中间结果是 KV Cache 树上的一棵子树，后续节点自动命中

五、具体效果

KV Cache 减少 67%（prefix sharing 效果）
JSON structured 生成 零 retry（vs 传统方法 20%+ retry 率）
Multi-hop 链式调用 ~2x 加速
首个将"生成"和"控制流"编译进同一执行引擎的系统

六、架构概览

SGLang 的完整执行流程：

SGLang Program
↓ 编译
Radix-Aware Scheduler
↓ 调度
LLM Engine (支持 FlashAttention / PagedAttention / TensorRT 等后端)

之前的工作（vLLM / Sarathi）注重单请求的显存和调度优化；SGLang 提升到程序级别：多个 LLM 调用之间的 KV Cache 共享和自动化并行。

七、历史影响

SGLang 重新定义了 LLM serving 的抽象层级——从"模型推理引擎"升级为"LLM 编程语言的运行时"。它的 prefix sharing 思路后来被多个框架采纳，structured generation 部分被 integrated 进 vLLM 的 guided decoding 模块。目前 SGLang 已发展成与 vLLM 并立的主流推理框架。