SGLang

01. 论文概览

论文：SGLang: Efficient Execution of Structured Language Model Programs
代码：sgl-project/sglang

02. 背景与预备知识

语言模型应用常由多次调用组成：例如先检索资料，再生成答案，或将任务拆成并行分支后汇总。这些调用往往重复使用系统提示、示例或对话历史。若每次都从头处理相同前缀，就会产生重复计算。

理解后文只需区分两个推理阶段：预填充（prefill）处理输入提示并生成键值缓存（KV cache）；解码（decode）利用已有缓存逐个生成新 token。KV 缓存保存注意力所需的中间结果，使模型不必在每一步重新计算整个历史。

论文的关键思路是把这些共享前缀组织成树，跨请求保留和查找对应的 KV 缓存；它还利用程序的并行结构与输出格式约束减少额外工作。接下来先看前端如何表达多调用程序，再看运行时如何执行。

03. 编程模型：把依赖关系暴露出来

一项任务可能需要多次调用模型。SGLang 的前端让你在 Python 中写清楚：先做什么、哪些步骤可以同时做、最后要等哪些结果。论文用一个作文评审程序说明这个过程（Fig. 2）。

图中的先后关系就是依赖关系：评审能否开始，取决于相关性判断；最终汇总，取决于三个评审的结果。三个评审彼此不需要等待，所以可以同时进行。

代码里，select 用于从候选项中选择，gen 用于生成文本，fork 用于创建并行分支。程序读取某个尚未生成的结果时会等待；不需要它的其他工作则可以继续执行。

这些信息也能帮助运行时：三个分支一开始有相同的提示，运行时可以尝试复用其前缀缓存；JSON 格式则为约束解码提供规则。论文实验默认使用解释器执行程序；后文将分别介绍前缀缓存和受约束解码的实现机制。

04. RadixAttention：以树管理跨请求缓存

问题：共享前缀会在不同层次出现

多个请求可能共享系统提示；相同 few-shot 例子之下又有不同问题；同一问题还可能分出多条采样路径。简单的整条请求缓存只能命中完全相同的请求，而只缓存一个固定系统提示又无法表达动态的多级分支。论文的方案把每条 token 路径组织进压缩前缀树（radix tree）。

每条边可以代表一段连续 token，关联其 KV 缓存位置；多个请求沿相同路径引用公共前缀。新请求到来时，从根开始寻找最长匹配；若匹配发生在边的中间，就将边拆分，使共享部分成为单独的祖先。论文 Fig. 3 展示了会话、few-shot、分支采样交替到来时的插入、拆分与淘汰过程。

根
 └── [S + 问题 A] → KV(S + A)

根
 └── [S] → KV(S)
      ├── [问题 A] → KV(A)
      └── [问题 B] → KV(B)

根
 └── [S] → KV(S)
      └── [问题 B] → KV(B)

回收：[问题 A] → KV(A)

根
 └── [S] → KV(S)
      ├── [问题 B] → KV(B)
      └── [问题 C] → KV(C)

因此，树本身是缓存的索引和共享关系：从根到某个位置的路径表示一个 token 前缀；分叉表示共享部分之后出现不同后缀；拆分让公共部分成为共同祖先；叶子淘汰则优先保留仍可能被其他分支使用的祖先。树节点记录缓存位置和管理信息，实际 KV 张量存放在缓存内存中。

缓存生存期与内存回收

根
 └── S 公共前缀  🔒
      ├── A 后缀  ○ 空闲叶子
      └── B 后缀  🔒 运行中

根
 └── S 公共前缀  🔒
      └── B 后缀  🔒 运行中

释放：A 的 KV 缓存空间

论文实现以最近最少使用（LRU）为淘汰原则，先回收不再被运行中请求引用的叶节点。优先淘汰叶节点可以保留公共祖先，直到祖先本身成为可淘汰叶节点。节点引用计数保护正在使用的路径；缓存和运行中的请求共享内存池，不为缓存预留固定容量，内存紧张时可让位于新批次（§3）。

这种设计改善的是前缀复用和内存共享，不意味着一次命中就可跳过整个请求。若请求长度为 N，命中前缀长度为 L，仍需处理后缀；原文用 token 比例定义缓存命中率：

这个指标按 token 加权，不是命中请求数除以总请求数，也不直接等同于计算时间节约比例。命中越长通常越有利于 prefill，但实际延迟仍由批次、解码和设备利用率等因素决定。

缓存感知调度与理论边界

A1  计算前缀 A
 ↓
B1  计算前缀 B，A 可能被挤出
 ↓
A2  A 若已被挤出，需重新计算
 ↓
B2  B 若已被挤出，也需重算

A1  计算并缓存前缀 A
 ↓
A2  命中并复用前缀 A
 ↓
B1  计算并缓存前缀 B
 ↓
B2  命中并复用前缀 B

根
 ├── 前缀 A
 │    ├── 请求 A1
 │    └── 请求 A2
 └── 前缀 B
      ├── 请求 B1
      └── 请求 B2

队列中若有多个等待请求，论文优先执行已缓存前缀更长的请求，以增加缓存局部性。其定理 3.1 在离线批处理、缓存容量至少等于最长请求长度等假设下，指出按树的深度优先顺序访问可以达到最优命中率，并将最长共享前缀优先与深度优先次序联系起来。

证明的直观要点是：在满足条件时，一条边的 KV 只需首次访问时计算一次。令 T 为所有请求形成的前缀树、|e| 为边 e 的 token 数，C 为需要计算的 prefill token 数，则该理想化模型有：

左式是必须覆盖所有不同树边的下界；右式表示理想 DFS 达到下界。其对应的最优命中率可写为：

这不保证在线业务总是最优：请求持续到达，输出长度事先未知，且批处理和公平性约束会打断理想访问顺序。论文还指出贪心调度可能使某些请求饥饿（§3、附录 A.3）。

源码对应：前缀匹配与回收

以下是某个固定提交的摘录，展示概念对应关系；工程版本支持可配置页面大小和淘汰策略，不能倒推论文实验版本的所有细节。代码链接保留固定提交与行号。

while len(key) > 0 and child_key in node.children.keys():
    child = node.children[child_key]
    child.last_access_time = access_time
    prefix_len = child.key.match(key, page_size=self.page_size)
    if prefix_len < len(child.key):
        new_node = self._split_node(child.key, child, prefix_len)
        value.append(new_node.value)
        node = new_node
        break
    else:
        value.append(child.value)
        node = child
        key = key[prefix_len:]

radix_cache.py:663–675：逐边比较，部分匹配时拆分节点；完全匹配则累积缓存并继续向下。

leaves = list(self.evictable_leaves)
eviction_heap = [
    (self.eviction_strategy.get_priority(node), node) for node in leaves
]
heapq.heapify(eviction_heap)
# ...
_priority, x = heapq.heappop(eviction_heap)
self.token_to_kv_pool_allocator.free_segment(x.value, start_pos=0)
num_evicted += len(x.value)
self._delete_leaf(x)
if len(x.parent.children) == 0 and x.parent.lock_ref == 0:
    new_priority = self.eviction_strategy.get_priority(x.parent)
    heapq.heappush(eviction_heap, (new_priority, x.parent))

radix_cache.py:563–580：此摘录省略了循环行，展示按策略选择可淘汰叶节点、释放缓存，以及未锁定父节点变成叶节点后进入候选集。

05. 压缩有限状态机：跳过确定文本

假设程序要求模型输出 {"grade": "A"}：花括号、字段名 grade 和引号由格式规定，模型真正需要选择的是等级，例如 A 或 B。压缩有限状态机（compressed FSM）的想法是：格式已经确定的部分不必逐个 token 让模型选择，可合并处理并更新模型状态；到有分支的地方，再让模型决定。

生成固定片段的一部分 → 检查
           ↓
生成固定片段的下一部分 → 检查
           ↓
选择 A 或 B → 检查 → 继续

固定：{"grade": "  →  跳过
           ↓
选择：A 或 B       →  模型决定
           ↓
固定："}           →  跳过

状态机在这里做什么？

可以把有限状态机理解为一张“合法输出路线图”：每个位置记录目前输出到哪里，箭头表示接下来允许出现什么。普通方法沿路线一步步检查；压缩方法把中间没有选择的连续路线合成一条长箭头。

效果和边界

论文在指定的 JSON 解码基准上报告，压缩 FSM 带来 1.6 倍吞吐量。状态机也需要预处理；论文指出，如果每个请求都重新预处理而不在批次间复用，吞吐量会降低 2.4 倍（§6.3）。因此，固定文本越多不自动意味着端到端收益一定越大，仍需结合请求和预处理成本测量。

还有一个技术细节：格式规则描述的是字符，而模型处理的是 token，两者边界可能不同。论文使用重新分词处理跳转文本；作者也指出，某些候选文本的 token 切分可能使概率分布产生偏差。格式合法只说明输出满足约束，并不保证内容正确。（附录 B）

06. API 推测执行：提前生成并验证

对于仅能通过 API 调用的模型，系统无法修改内部 KV 管理或解码器。论文提出另一种推测：例如程序依次生成 name 和 job，第一次请求可忽略原本的停止位置，多生成一段；解释器随后尝试把额外输出与下一段模板匹配，如果匹配成功则复用，减少后续 API 调用。

这种机制的收益来自跨调用摊销上下文输入和网络往返，不是常说的“小模型草稿 + 大模型验证”的 token 级推测解码。推测失败则不能获得相同收益；输出是否匹配、提示设计和提供商计费方式都会影响结果。论文在 GPT-3.5 的三字段抽取示例中报告输入 token 成本约降低三倍，不能推广为所有模型、价格或任务均节省三倍（§5、§6.2）。

07. 实验：结果、对照与解释

论文以 programs/s 衡量大量程序实例批量运行时的最大吞吐量；单程序重复运行的平均耗时用于延迟。主要实验包括单张 A10G 上的 Llama-7B、多卡张量并行的 Mixtral-8x7B 和 Llama-70B、图像视频模型，以及 GPT-3.5 API。比较对象包括论文当时的 vLLM 0.2.5、Guidance 0.1.8 和 LMQL 0.7.3，且部分工作负载因功能或性能原因没有完整基线（§6.1、Fig. 5–7）。

短输出多轮聊天受益尤其容易理解：历史对话重复 prefill 的比例较高，缓存命中后可以减少大量重复前缀计算；长输出场景中，后续逐 token decode 占比上升，而不同会话之间共享有限，因此论文观察到几乎没有加速（§6.2）。这说明缓存命中率不是脱离工作负载即可预测的端到端收益。

消融实验 Fig. 8(c) 分别移除缓存、树结构、缓存感知调度、前端并行及 fork hint。它支持的结论是：在选定任务中，这些组件的组合有助于达到最佳结果；并不意味着每个组件在所有任务上的收益一致或相互独立。Fig. 8(a)(b) 通过部分禁用匹配 token 改变命中率，显示更高命中率与更大批次、更高吞吐及更低延迟相关。

多模态对照

数据来自原文 Table 2；比值由表内四舍五入数字计算。两行单位不同，不能直接比较绝对数值。

图像任务中同一图片对应多个问题，因此图片 token 的 KV 也有复用机会；论文使用图片哈希参与缓存键。该实验以模型作者的 Hugging Face Transformers 实现为基线，而不是同一时期所有多模态推理框架的全面排名。论文文字称“最高 6×”，表内数字直接相除约为 6.39×，两者可能涉及取整，故分别保留（§6.2、Table 2）。

08. 局限、适用边界与启示

作者提出的限制。贪心前缀调度可能饿死其他请求；论文将与公平调度结合列为未来工作。缓存层级扩展、语义模糊匹配、更多输出模态以及更强的编译期优化也未在论文中解决（§8）。这些是论文版本的研究边界，而不是对后续产品能力的断言。

压缩 FSM 对 tokenization 的处理仍可能扭曲选项概率，尤其当备选字符串映射为不同 token 路径时；符合格式也不保证内容真实或业务语义正确。附录 D 的 GPT-4 提示词重排尝试中，15 个测试模板有 12 个被人工确认语义未改变；重排属于激进优化，剩余失败说明不能把自然语言顺序调整当成严格等价变换。

独立判断。原文对比的是特定时间点的软件与硬件：例如 vLLM 0.2.5 与 7B/A10G 环境。论文注释还说明较新的 vLLM 当时已部分集成可选前缀缓存。因此，这些数字适合证明当时的设计有效性，不能直接代表今天各推理引擎的相对性能。Agent trace 重放也不完全等同于真实在线系统中的动态到达、工具耗时和尾延迟。

从系统设计看，最适合优先考虑前缀复用的是提示长、公共前缀稳定、并发请求有局部性的场景；要评价实际收益，应同时测量前缀命中 token 比例、首 token 延迟、端到端延迟、吞吐和公平性。请求很短、前缀缺乏重合或长输出占主导时，KV 复用的收益可能较小；这是一种从工作负载结构出发的推断，具体幅度仍需实测。

论文的主要贡献是把语言程序的结构与推理运行时连接起来：前端表达调用关系，运行时利用前缀树维护可复用状态，并为结构化输出与黑盒 API 设计不同的加速路径。其价值不仅是一个最高加速数字，更是展示了工作流信息如何改变推理系统的调度与缓存决策。

参考文献

1. SGLang: Efficient Execution of Structured Language Model Programs（arXiv v2） · 论文 PDF
2. SGLang 官方代码仓库