# 2312.07104_SGLang❇️: Efficient Execution of Structured Language Model Programs * 首页: * PDF: * 引用: 182(2025-08-16) * 组织: * 1 Stanford University   * 2 UC Berkeley   * 3 Shanghai Jiao Tong University * 4 Texas A&M University   * 5 Independent Researcher * GitHub: * SGLang: Structured Generation Language ## 总结 RadixAttention * 核心思想 * 在运行时自动保留并复用KV缓存，而不是像传统方式那样在请求完成后丢弃缓存 * 数据结构 * 使用 radix tree（基数树） 来管理KV缓存 速度高效的原因 * KV 缓存复用 * 调度优化 * 解码加速 贡献 * 首次提出将KV缓存（Key-Value Cache）视为基于树结构的LRU缓存（Least Recently Used Cache），是支持多级共享、缓存感知调度、前端与运行时协同调度、以及分布式场景的首个解决方案。 ## OpenAI GPT-4总结 ### 1. 论文速览（20秒内可理解） 📌 **研究类型**： - 领域标签：NLP/机器学习 - 任务类型：模型优化/实验分析 🌍 **现实意义**：该研究提出了一种新的系统SGLang，能够有效执行复杂的语言模型程序，对于提高大型语言模型的执行效率具有重要价值。 ### 2. 核心创新（对比现有方法） ✨ **技术突破**： - 方法创新点：SGLang系统包括一个前端语言和一个运行时，前端简化了编程过程，运行时通过RadixAttention和压缩有限状态机等优化技术加速了执行过程。 - 数据/实验设计的独特性：实验表明，SGLang在各种大型语言和多模态模型的任务上，与最先进的推理系统相比，吞吐量提高了高达6.4倍。 ⚠️ **作者自述局限**：论文并未明确提到任何限制。 ### 3. 核心价值： - 解决了什么问题？对谁有用？ SGLang解决了大型语言模型执行效率低下的问题，对于需要使用大型语言模型进行复杂任务的研究者和开发者有用。 - 方法论的新颖性 SGLang的新颖之处在于它将语言模型的执行过程视为一个程序，通过引入新的优化技术，提高了执行效率。 ### 4. 精读决策指南 🔍 **推荐指数**：★★★★☆ 如果你在研究大型语言模型的执行优化，或者你的工作需要使用大型语言模型进行复杂任务，那么这篇论文值得你仔细阅读。 ## Qwen-Plus总结 ### 1. 论文速览（20秒内可理解） 📌 **研究类型**： - 领域标签：**NLP / 机器学习系统** - 任务类型：**模型优化 / 系统设计 / 实验分析** 🌍 **现实意义**： SGLang 提供了一种高效执行复杂语言模型程序的系统，显著提升多轮生成任务的吞吐量，对构建智能代理、多模态应用和结构化输出任务具有重要工业价值。 --- ### 2. 核心创新（对比现有方法） ✨ **技术突破**： - **方法创新点**： - 引入 **RadixAttention** 机制，实现 KV 缓存的高效复用，减少重复计算。 - 提出 **压缩有限状态机（Compressed FSM）**，实现结构化输出（如 JSON）的快速解码。 - 支持 API-only 模型的 **推测执行（Speculative Execution）**，优化多调用流程。 - **数据/实验设计的独特性**： - 在多种大语言模型（Llama-7B/70B、Mistral、LLaVA 等）和多模态任务上进行了广泛实验。 - 对比了多个当前主流系统（如 vLLM、LMQL），展示了显著性能提升（最高 6.4 倍吞吐量）。 ⚠️ **作者自述局限**： - 当前系统主要面向结构化语言模型程序（LM Programs）优化，对非结构化任务的优化效果未明确评估。 - 依赖 Python 嵌入式语言，可能对非 Python 用户不够友好。 --- ### 3. 核心价值： - **解决了什么问题？对谁有用？** SGLang 解决了当前语言模型程序执行效率低、开发复杂的问题，适用于需要多轮生成、结构化输出、多模态处理的场景，如智能代理、多模态推理、结构化输出生成等。 - **方法论的新颖性** 通过系统性地利用 LM Programs 的多调用结构，提出前端语言 + 后端优化的双层架构，并引入 RadixAttention 和 FSM 解码等创新技术，实现了性能与开发效率的双重提升。 --- ### 4. 精读决策指南 🔍 **推荐指数**：★★★★☆ - 如果你是 **NLP 系统工程师 / 大模型部署者 / 智能代理开发者**，这篇论文值得精读，尤其是你关注 **多调用语言模型程序的执行效率**。 - 如果你主要研究 **模型架构 / 理论分析 / 单模型推理**，则可略读或仅关注实验部分。 ## Abstract **Abstract** 部分介绍了当前大语言模型（LLMs）在处理复杂任务时所面临的问题和 SGLang 系统的解决方案。 **问题背景**： 大语言模型越来越多地被用于需要多次生成调用、高级提示技术、控制流和结构化输入/输出的复杂任务。然而，目前缺乏高效的系统来编程和执行这些应用。 **解决方案**： 为此，作者提出了 **SGLang**，一个高效的复杂语言模型程序执行系统。SGLang 包括两个主要部分： 1. **前端语言**： 通过提供生成和并行控制的基本操作（primitives），简化编程过程。这部分强调了前端对开发者的友好性。 2. **运行时系统（Runtime）**： 这是 SGLang 的核心部分，通过一些创新优化来加速执行，**重点包括**： - **RadixAttention**：用于 KV 缓存的重用，提高效率。 - **压缩有限状态机**：用于更快速的结构化输出解码。 **实验结果**： 实验表明，SGLang 在各种大型语言和多模态模型上，相比最先进的推理系统，在多个任务中实现了高达 **6.4 倍的吞吐量提升**。这些任务包括： - Agent 控制 - 逻辑推理 - 少样本学习基准 - JSON 解码 - 检索增强生成（RAG）流程 - 多轮对话等 **重点强调**： SGLang 的创新点主要在于其高效的运行时优化（如 RadixAttention 和压缩有限状态机），以及在多种复杂任务上的显著性能提升，是本文的核心贡献。 ## 1 Introduction 随着大语言模型（LLM）能力的提升，其应用场景也得到了扩展，能够处理更广泛的一般任务，并作为**自主代理（autonomous agents）**运行。这类应用中，LLMs需要进行多轮的**规划、推理和与外部环境的交互**。实现这一目标的关键方法包括： - **工具使用（tool usage）**：如 ToolFormer 和 Gorilla，通过调用外部工具完成任务； - **多模态输入（multiple input modalities）**：如 Gemini 和 Flamingo，支持图像、文本等多种输入形式； - **多种提示技术（prompting techniques）**：如 Few-Shot Learning、Self-Consistency、Skeleton-of-Thought、Tree-of-Thought 等，以提高推理能力。 这些新用例通常需要**多次、依赖性强的 LLM 生成调用**，体现出一种**使用多调用结构（multi-call structures）来完成复杂任务**的趋势，例如 REACT 和 LLM-Driven Workflows。 --- ### 语言模型程序（LM Programs） 这些多调用结构的应用，标志着我们与 LLM 的交互方式从**简单的聊天**转变为一种**程序化的方式**，即通过程序来**调度和控制 LLM 的生成过程**。这种程序被称为“**Language Model Programs（LM Programs）**”，相关技术包括 LMQL 和 DSPy。 **LM Programs 的两个主要特点**： 1. **包含多个 LLM 调用，并结合控制流**（如循环、条件判断），用于完成复杂任务并提高整体质量； 2. **输入和输出结构化**，便于程序组合和系统集成。 --- ### 当前挑战（Challenges） 尽管 LM Programs 被广泛使用，但目前的系统在**表达与执行上仍存在效率问题**，主要体现在两个方面： #### 1. **开发难度大** - LLM 的输出具有**非确定性**，编写 LM Programs 需要进行大量的**字符串处理、提示调优、输出解析**； - 支持**多模态输入**和**并行机制**，增加了程序复杂性； - 使得即使是简单的程序也难以被清晰表达和维护。 #### 2. **执行效率低** 当前主流的 LLM 推理引擎（如 vLLM、TGI、TensorRT-LLM）虽然优化了**延迟和吞吐量**，但它们缺乏对**工作负载结构的了解**，导致执行效率低下。具体表现如下： - **KV 缓存（KV Cache）无法复用**：多个 LLM 调用之间可能共享前缀，但当前系统无法有效复用缓存，导致重复计算和内存浪费； - **约束解码效率低**：在生成结构化输出（如 JSON）时，只能逐个解码 tokens，效率低下。 --- ### SGLang：解决方案 为解决上述问题，本文提出了 **SGLang（Structured Generation Language）**，一种用于 LLM 的结构化生成语言。SGLang 的核心思想是**系统化地利用 LM Programs 中的多调用结构**来提高执行效率。 SGLang 包括两个部分： - **前端语言**：简化 LM Programs 的编程； - **后端运行时**：加速其执行。 这两部分可协同工作，也可独立使用。 #### 前端语言（Front-end） SGLang 是一种嵌入在 Python 中的**领域特定语言（DSL）**，提供以下关键操作： - **生成原语**（如 `extend`、`gen`、`select`）； - **并行控制**（如 `fork`、`join`）； - 支持 Python 的控制流和库，便于开发复杂提示流程。 SGLang 提供了**解释器与编译器**，其中解释器通过异步执行原语操作，管理程序的同步和并行。 #### 后端运行时优化（Runtime Optimizations） SGLang 在运行时引入了三种关键优化技术： 1. **RadixAttention（基数注意力）**： - 解决 KV 缓存复用问题； - 通过**基数树（radix tree）管理缓存**，支持高效匹配、插入和驱逐； - 可自动识别并复用多个调用中共享的缓存，提升执行效率。 2. **压缩有限状态机（Compressed Finite State Machine）**： - 用于**结构化输出的解码加速**（如 JSON）； - 传统系统只能逐个 token 解码，而 SGLang 通过构建压缩状态机，**将多个 token 解码路径压缩为一步**，实现并行解码。 3. **API 推测执行（API Speculative Execution）**： - 为仅提供 API 接口的模型（如 GPT-4）优化多调用程序执行。 --- ### 应用与实验结果（Applications and Evaluation） SGLang 已被应用于多个 LLM 场景，包括： - 代理控制、逻辑推理、few-shot 学习基准、JSON 解码、检索增强生成、多轮对话、多模态处理等。 在多个模型（如 Llama-7B/70B、Mistral-8x7B、LLaVA 系列）和 GPU 硬件（A10G/A100）上测试，**SGLang 相比现有系统（Guidance、vLLM、LMQL）的吞吐量最高提升了 6.4 倍**。 --- ### 总结（重点） - **LLMs 正从聊天工具演进为程序化工具**，通过 LM Programs 实现复杂任务的自动化处理； - 当前的 LM Programs **开发复杂、执行效率低**，主要问题包括 KV 缓存复用和结构化解码效率； - SGLang 通过**结构化语言 + 高效运行时优化**，解决了上述问题，显著提升了执行效率； - 实验表明，SGLang 在多模型、多任务、多硬件环境下的**性能优势显著**。 ## 2 Programming Model ![](https://img.zhaoweiguo.com/uPic/2025/08/zr0MQq.png) Figure 2:The implementation of a multi-dimensional essay judge in SGLang utilizes the branch-solve-merge prompting technique saha2023branch. Primitives provided by SGLang are shown in red. 本节介绍了 **SGLang 编程模型**，通过**运行示例**展示了其语言原语与执行模式，并概述了**运行时优化**的潜力。该编程模型通过提供灵活且可组合的原语，简化了多轮调用工作流中的繁琐操作（例如字符串操作、API 调用、约束定义、并行化等）。 --- ### 一个运行示例 SGLang 是一个**嵌入在 Python 中的领域特定语言（DSL）**。图 2 展示了一个使用 **branch-solve-merge 提示技术** 的多维作文评分程序。 函数 `multi_dimensional_judge` 有三个参数：`s`（提示状态）、`path`（图像路径）和 `essay`（作文文本）。通过 `+=` 操作符，可以将字符串和 SGLang 原语添加到状态 `s` 中以执行。 程序的执行流程如下： 1. 将图像和作文添加到提示中； 2. 使用 `select` 判断作文是否与图像相关，结果存储在 `s["related"]`； 3. 如果相关，提示被“分支”为三个副本，**并行评估不同维度**，使用 `gen` 存储结果到 `f["judgment"]`； 4. 合并判断结果，生成摘要并给出字母等级； 5. 最终返回符合正则表达式约束的 JSON 格式结果。 **重点**：SGLang 显著简化了这类程序的编写。若使用 OpenAI API 类接口实现相同功能，需要 2.1 倍的代码行数，因为需要手动处理字符串和并行控制。 --- ### 语言原语 SGLang 提供了控制提示状态、生成和并行化的原语，并可与 Python 语法和库结合使用。主要原语包括： - **gen**: 调用模型生成内容，并将结果存储在指定变量中。支持通过 `regex` 参数对输出施加约束（如 JSON Schema）。 - **select**: 调用模型从选项列表中选择概率最高的选项。 - **+= / extend**: 将字符串追加到提示中。 - **[variable_name]**: 获取生成结果。 - **fork / join**: 创建并重新合并提示状态的并行分支。 - **image / video**: 接收图像和视频输入。 **重点**：这些原语提供了对提示状态的细粒度控制，是 SGLang 的核心能力之一。 --- ### 执行模式 SGLang 程序可以通过两种方式执行： 1. **解释器模式**：将提示视为异步流，`extend`、`gen`、`select` 等原语提交到流中异步执行。非阻塞调用允许 Python 代码继续运行。每个提示由后台线程中的流执行器管理，支持程序内的并行性。获取生成结果将阻塞，直到结果就绪。 **类比**：这种方式类似于异步启动 CUDA 内核。 2. **编译模式**：程序可编译为计算图，通过图执行器运行，从而实现更多优化。本文默认使用解释器模式，编译模式的评估结果见附录 D。 此外，SGLang 支持开源模型（通过其自研运行时 SRT）和 API 模型（如 OpenAI 和 Anthropic）。 --- ### 与其他系统的比较 LLM 编程系统可分为两类： - **高层系统**：如 LangChain、DSPy，提供预定义或自动生成的提示。例如，DSPy 有提示优化器。 - **低层系统**：如 LMQL、Guidance、SGLang，不改变提示，允许直接操作提示和原语。 SGLang 属于低层系统，**更多关注运行时效率**，并配有专门设计的运行时，支持本文后续介绍的新颖优化。高层语言（如 DSPy）可以编译为低层语言（如 SGLang）。第 6 节展示了将 SGLang 作为 DSPy 后端的例子。 表 1 对比了 LMQL、Guidance 和 SGLang 的特性： | 系统 | 语法 | 语言原语 | 运行时后端 | |----------|----------|------------------------------------------|---------------------------------------------| | LMQL | 自定义 | extend, gen, select | HF Transformers, llama.cpp, OpenAI | | Guidance | Python | extend, gen, select, image | HF Transformers, llama.cpp, OpenAI | | SGLang | Python | extend, gen, select, image, video, fork, join | SGLang Runtime (SRT), OpenAI | **重点**：SGLang 提供了更丰富的并行控制能力（如 `fork`/`join`），并有自己的高效运行时。 --- ### 运行时优化 图 2 中展示了三个运行时优化机会： - **KV 缓存重用** - **快速约束解码** - **API 推测执行** 这些优化将在后续章节中详细讨论。 ## 3 Efficient KV Cache Reuse with RadixAttention 本节介绍了 **RadixAttention**，这是一种用于在运行时自动、系统性地复用KV缓存（Key-Value Cache）的新技术。该方法旨在优化SGLang程序中多个生成调用和实例之间的KV缓存复用，从而减少重复计算和内存占用。 --- ### **KV缓存复用的背景与挑战** 在大型语言模型（LLM）的推理过程中，**KV缓存**存储了前向传播过程中的中间张量，并用于解码后续的token。由于KV缓存的计算仅依赖于前缀token，因此具有相同前缀提示的不同请求可以共享KV缓存。这一特性带来了很多缓存复用的机会。 然而，现有系统在处理KV缓存复用时存在局限性。例如，它们通常需要**手动配置**，且难以处理**动态树结构**等复杂模式。因此，大多数系统选择**重新计算KV缓存**，而不是复用，这导致了性能和资源的浪费。 --- ### **RadixAttention 的核心思想与实现** **RadixAttention** 的核心思想是：**在运行时自动保留并复用KV缓存**，而不是像传统方式那样在请求完成后丢弃缓存。 - **数据结构**：系统使用 **radix tree（基数树）** 来管理KV缓存。这是一种高效的空间压缩树结构，支持快速的前缀匹配、插入和复用。 - **缓存存储方式**：KV缓存以“分页”方式存储，每页对应一个token。这样可以灵活管理GPU内存。 - **内存管理策略**： - 采用 **LRU（Least Recently Used）** 策略进行缓存淘汰，优先淘汰最近最少使用的叶节点。 - 节点维护**引用计数器**，只有当引用计数为0时才可被回收。 - 系统**不预先分配固定大小的缓存池**，而是与正在运行的请求**共享同一块内存池**，实现动态内存分配。 - **前端提示机制**（Frontend Hint）：前端在执行 `fork` 操作时，会先发送前缀提示，帮助运行时快速建立树结构，从而提升匹配效率。 - **图示说明**（见图3）：演示了多个请求在不同时刻的radix树演化过程，包括插入、复用、分裂和淘汰等操作。 ![](https://img.zhaoweiguo.com/uPic/2025/08/SL2IYm.png) Figure 3: Examples of RadixAttention operations with an LRU eviction policy, illustrated across nine time points. * 图解 * 每条树边都带有一个标签， * 表示一个子字符串或一个标记序列 * 节点采用颜色编码以反映不同的状态： * 绿色表示新添加的节点， * 蓝色表示在该时间点访问过的缓存节点， * 红色表示已被驱逐的节点。 * 步骤详解 * 在步骤 (1) 中，基数树最初为空。 * 在步骤 (2) 中，服务器处理传入的用户消息“Hello”，并以 LLM 输出“Hi”进行响应。系统提示“You are a helpful assistance”（您是一位乐于助人的助手）、用户消息“Hello!”和 LLM 回复“Hi!”被合并到树中，作为一条指向新节点的边。 * 在步骤 (3) 中，一个新的提示到达，服务器在基数树中找到该提示的前缀（即对话的第一个轮次），并重用其键值缓存。新的轮次将作为新节点附加到基数树中。 * 在步骤 (4) 中，开始一个新的聊天会话。步骤 (3) 中的节点“b”被拆分为两个节点，以允许两个聊天会话共享系统提示。 * 在步骤 (5) 中，第二个聊天会话继续进行。但是，由于内存限制，步骤 (4) 中的节点“c”必须被移除。新的轮次将附加到步骤 (4) 中的节点“d”之后。 * 在步骤 (6) 中，服务器接收一个少样本学习查询，对其进行处理，并将其插入到树中。由于新查询与现有节点不共享任何前缀，因此根节点被拆分。 * 在步骤 (7) 中，服务器接收一批额外的少样本学习查询。 这些查询共享同一组小样本示例，因此我们将节点“e”从 (6) 中拆分出来以实现共享。 * 在步骤 (8) 中，服务器从第一个聊天会话收到一条新消息。它会驱逐第二个聊天会话中的所有节点（节点“g”和“h”），因为它们是最近最少使用的。 * 在步骤 (9) 中，服务器收到一个请求，要求从 (8) 中为节点“j”中的问题采样更多答案，这可能是为了实现自洽性提示。为了给这些请求腾出空间，我们驱逐了 (8) 中的节点“i”、“k”和“l”。 --- ### **缓存感知调度策略（Cache-aware Scheduling）** 为了最大化KV缓存的命中率，系统引入了**缓存感知调度算法**。 - **定义**：缓存命中率 = 已缓存的提示token数 / 总提示token数。 - (number of cached prompt tokens)/(number of prompt tokens) - **调度原则**： - 在批处理场景中，**按最长共享前缀优先**（longest-shared-prefix-first）排序请求，而不是采用先到先服务（FIFO）。 - 该策略与**深度优先搜索（DFS）顺序**等价，从而在离线情况下可实现最优缓存命中率（定理3.1）。 - **定理3.1**（Theorem 3.1）： > 对于一批请求，当缓存大小 ≥ 最长请求长度时，按照radix树的DFS(depth-first search)顺序执行请求可实现最优缓存命中率。最长共享前缀优先顺序等同于深度优先搜索顺序。 - **在线场景**：系统在实际运行中无法完全遵循DFS顺序，但通过调度策略**模拟DFS行为**，仍能保持较高的缓存命中率。 - **局限性**：贪心式调度可能导致**饥饿问题**（某些请求长期得不到执行），未来将结合**公平调度算法**优化。 --- ### **分布式扩展（Distributed Cases）** RadixAttention 可扩展到多GPU和分布式环境： - **Tensor 并行**：每个GPU维护自己的KV缓存分片，无需额外同步，结构操作一致。 - **数据并行**：多个工作节点的RadixAttention实现可参考附录A.4部分。 --- ### **总结（重点内容强调）** - **核心贡献**：RadixAttention 实现了KV缓存的**自动复用**，通过 radix tree 结构和缓存感知调度策略，显著提升了LLM推理效率。 - **关键技术点**： - **radix tree** 用于高效组织和复用KV缓存； - **LRU + 引用计数** 实现内存管理； - **缓存感知调度** 提升缓存命中率； - **分布式支持** 保证系统可扩展。 - **优势**：相比现有系统无需手动配置、支持复杂结构、内存开销低。 --- ### **不重要内容精简说明** - 附录A中关于KV缓存背景和定理的证明，仅在需要时参考，正文重点在于实现机制和调度策略。 - 图3的具体示例流程仅为辅助理解，重点在于**radix tree的动态维护机制**和**缓存复用的逻辑**。 ## 4 Efficient Constrained Decoding with Compressed Finite State Machine ### 4 高效的有限状态机压缩约束解码 在语言模型（LM）程序中，用户常常希望限制模型的输出遵循特定格式，例如 JSON Schema。这种限制可以提高输出的可控性和鲁棒性，并使其更易于解析。SGLang 提供了一个 **regex 参数**，通过正则表达式来强制这些限制，正则表达式在许多实际场景中已经足够表达。 ### 现有系统的约束解码方法 现有系统通常通过将正则表达式转换为**有限状态机（FSM）** 来实现这种约束。在解码过程中，系统会维护当前的 FSM 状态，从下一状态中获取允许的 token，并将不符合约束的 token 的概率设为零，逐 token 解码。然而，这种**逐 token 解码**的方式在某些情况下效率不高，尤其是当多个 token 可以同时解码时。 例如，在 `"summary": " ` 这样的固定序列中，虽然在常规解码过程中需要多个步骤，但实际上每一步只有一个有效 token，因此整个序列可以**一次性解码完成**（即一次前向传播）。但现有系统由于 FSM 和模型运行器之间缺乏集成，**无法进行多 token 并行处理**，导致解码速度较慢。 ### SGLang 的高效解码方法 ![](https://img.zhaoweiguo.com/uPic/2025/08/pIbehl.png) Figure 4:The decoding process of normal and compressed FSMs (the underscore _ means a space). SGLang 通过构建一个**快速的约束解码运行时**，利用**压缩有限状态机（Compressed FSM）** 克服了这一限制。该运行时会对 FSM 进行分析，并将**连续的单 token 转移边**压缩为单个边，如图 4(b) 所示。这种方式使得系统能够识别哪些 token 可以**一起解码**。 如图 4(d) 所示，多个 token 可以在**一个前向传播步骤中完成解码**，从而显著提高了解码效率。该方法具有**通用性**，适用于所有的正则表达式。有关背景和实现细节，详见附录 B。 ## 5 Efficient Endpoint Calling with API Speculative Execution ### 5 利用 API 推测执行高效调用端点 本节在前文基础上，介绍了针对仅可通过 API 调用的模型（如 OpenAI 的 GPT-4）的优化方法。由于这类模型是黑盒，无法对推理过程进行修改，因此需要通过其他方式提升性能和降低调用成本。 **核心内容**是提出了一种新的优化方法：**API 推测执行**（speculative execution），用于加速多调用 SGLang 程序的执行，并降低 API 成本。 ### 优化动机 一个典型的 SGLang 程序可能会包含多个 `gen` 调用，如： ```python s += context + "name:" + gen("name", stop="\n") + "job:" + gen("job", stop="\n") ``` 如果没有优化，每个 `gen` 都会触发一次 API 调用，这样会导致： - **输入 token 费用重复计算**：`context` 部分会被多次传入，导致费用增加； - **调用延迟叠加**：多次 API 请求会增加整体响应时间。 ### 推测执行的原理 SGLang 提出的优化方法是在第一次调用时**启用推测执行**。具体做法是： - 忽略第一次调用中的 `stop` 条件； - 让模型继续生成比所需更多的 token； - 将这些额外的生成结果缓存起来； - 在后续的 `gen` 调用中**匹配并复用**这些缓存的输出。 ### 优势 如果提示词设计得当，模型能够**高准确率地匹配模板结构**，从而实现： - **减少一次 API 调用**：节省调用延迟； - **降低输入费用**：避免重复传入相同的 `context` 部分。 ### 总结 本节的重点是通过**API 推测执行**优化黑盒模型的多调用场景，其关键在于通过一次调用生成更多 token，后续通过缓存和复用来减少 API 调用次数，从而提升性能和降低成本。 ## 6 Evaluation 本节评估了 SGLang 在多种大型语言模型（LLM）工作负载中的性能，并通过消融实验和案例研究展示了其组件的有效性。SGLang 基于 PyTorch 实现，并使用了 FlashInfer 和 Triton 提供的定制 CUDA 内核。 --- ### 6.1 实验设置（Setup） #### **模型（Models）** 测试了多种模型，包括： - **稠密模型**：Llama-2（参数量 7B-70B） - **稀疏模型**：Mixtral - **多模态模型**：LLaVA（图像、视频） - **API 模型**：OpenAI 的 GPT-3.5 所有模型均采用 float16 精度进行运算。 #### **硬件（Hardware）** - **主要实验平台**：AWS EC2 G5 实例，配备 NVIDIA A10G GPU（24GB） - **大模型实验**：使用多张 A10G GPU 并启用张量并行（Tensor Parallelism） - **部分补充实验**：在 A100G（80GB）GPU 上进行 #### **基线（Baselines）** 与以下系统进行对比： - **Guidance**：用于控制 LLM 的语言，使用 llama.cpp 后端 - **vLLM**：高吞吐量的推理引擎 - **LMQL**：查询语言，使用 Hugging Face Transformers 后端 除非特别说明，所有系统使用默认设置以保证计算结果一致。 #### **工作负载（Workloads）** 测试了多种任务，包括： - **MMLU**（5-shot） - **HellaSwag**（20-shot） - **ReAct 代理**与**生成式代理** - **Tree-of-thought**（GSM-8K） - **Skeleton-of-thought**（生成提示） - **Branch-solve-merge**（LLM 判定） - **JSON 解码（带正则表达式约束）** - **多轮对话**（短输出和长输出） - **DSPy RAG 管道** #### **指标（Metrics）** - **吞吐量（Throughput）**：运行足够大的程序实例，计算每秒执行的程序数（p/s） - **延迟（Latency）**：单程序运行，计算平均延迟 --- ### 6.2 端到端性能（End-to-End Performance） #### **开源模型结果** - **图5和图6** 展示了 SGLang 在 Llama-7B 上的吞吐量和延迟。SGLang 相较于基线模型，**吞吐量提升最高达 6.4 倍，延迟降低最高达 3.7 倍**。 - **性能提升原因**： - **KV 缓存复用**：如 RadixAttention，有效减少内存使用和预填充计算 - **单程序内并行**：利用程序结构进行更高效的调度 - **受限解码加速**：如 JSON 解码中使用压缩有限状态机（CFSM）一次解码多个 token #### **多模态模型支持** - SGLang 支持图像和视频原语，可原生运行多模态模型（如 LLaVA） - 对于相同图像的多问题处理，SGLang 复用 KV 缓存，提升吞吐量 - **表2** 中比较了 SGLang 与原始实现的吞吐量，**SGLang 吞吐量最高提升 6 倍** #### **生产部署** - SGLang 部署在 Chatbot Arena，用于服务开源模型 - 在 LLaVA-Next-34B 和 Vicuna-33B 上观察到 **52.4% 和 74.1% 的 KV 缓存命中率** - 缓存命中主要来自系统消息、常见图像和多轮对话历史，**显著降低首 token 生成延迟（平均降低 1.7 倍）** #### **API 模型结果** - 使用 OpenAI 的 GPT-3.5 进行维基页面字段提取 - 通过少样本提示，提升了推测执行的准确性，并**将输入 token 成本降低约三倍** --- ### 6.3 消融实验（Ablation Study） #### **缓存命中率与性能的关系** - **图8（a）（b）** 显示：**缓存命中率越高，吞吐量越高，延迟越低**，批次大小也越大 - 通过部分禁用匹配 token 验证了缓存系统对性能的影响 #### **RadixAttention 的有效性** - **图8（c）** 展示了不同组件的消融实验结果，包括： - **不使用缓存** - **不使用树结构缓存** - **不使用缓存感知调度策略** - **不使用前端并行** - **不发送前端提示** - 实验结果表明：**所有组件对性能均有显著影响**，特别是前端提示与并行机制对运行时性能非常重要 #### **RadixAttention 的开销** - 在无缓存复用机会的基准测试中，RadixAttention 数据结构管理仅占 **0.3% 的开销** - 因树操作复杂度低，**RadixAttention 可以默认启用** #### **压缩有限状态机（CFSM）有效性** - 在 JSON 解码任务中，**CFSM 将吞吐量提升 1.6 倍** - 预处理后复用状态机是关键，否则每请求预处理会**使吞吐量降低 2.4 倍** --- ### 总结 本节通过多个实验验证了 SGLang 在 LLM 执行中的高效性，特别是在 KV 缓存复用、调度优化和解码加速方面表现突出。无论是在稠密模型、稀疏模型、多模态模型还是生产部署中，SGLang 都展现出显著性能优势。消融实验进一步验证了关键组件对性能的贡献，证明了 SGLang 前端语言与运行时协同设计的重要性。 ## 7 Related Work 本节总结了与本文工作相关的研究进展，重点突出了本文提出的 **RadixAttention** 和 **SGLang** 在KV缓存重用和编程模型优化方面的创新与优势。 --- ### RadixAttention 的创新点 本文首次提出将KV缓存（Key-Value Cache）视为基于树结构的LRU缓存（Least Recently Used Cache），是支持**多级共享、缓存感知调度、前端与运行时协同调度、以及分布式场景**的首个解决方案。这一设计能够更高效地管理缓存，在结构化推理任务中显著提升性能。 --- ### 其他相关工作分析 - **vLLM** 和 **ChunkedAttention** 研究了KV缓存的某些简单复用场景（如系统提示共享），但未涉及**多级树结构共享**或**LRU缓存机制**。 - **PromptCache** 提出了超出前缀范围的模块化缓存复用方法，但由于复用粒度较大，可能导致**高达43%的准确性下降**。 - **HydraGen、FlashInfer 和 ChunkedAttention** 的重点在于**CUDA内核优化**，并未引入LRU缓存的概念。 - **API Serve 和 LLM-SQL** 针对特定应用场景（如与外部API调用和数据库交互）研究KV缓存重用，但缺少**基数树结构**和**缓存感知调度**。 --- ### LLM 编程与代理框架 本节还对比了多个现有的大语言模型编程与代理框架，包括 **Guidance、LMQL、DSPy、LangChain、AutoGen 和 LLM Compiler**。 - **Guidance 和 LMQL** 与本文提出的 **SGLang** 最为相似，文章在[第2节](https://arxiv.org/html/2312.07104v2#S2)对此进行了详细比较。 - **SGLang** 的创新点在于提出了**新的运行时优化机制**，以加速结构化语言模型程序的执行。 - **SGLang** 不仅兼容其他框架（如DSPy），还支持多种常见推理优化技术，如 **vLLM、FlashAttention、KV量化、模型压缩等**。 --- ### 总结 本节强调了本文在KV缓存管理和语言模型编程方面的创新性，特别是 **RadixAttention** 在缓存结构设计上的突破，以及 **SGLang** 在编程模型和执行优化上的综合优势。相比现有工作，本文提出的方案在**效率、兼容性和准确性**上具有更全面的优势。 ## 8 Future Directions and Conclusion ### 未来方向 尽管 SGLang 在提升语言模型程序效率方面已取得一定进展，但仍存在一些局限性，这些局限性指出了未来研究的潜在方向： - **扩展 SGLang 的输出模态**：当前 SGLang 主要面向语言类输出，未来可以扩展其支持更多的输出模态（如图像、音频等），以增强其多功能性。 - **适配不同内存层次的 RadixAttention**：将 RadixAttention 优化为能够在多种内存层次（如 DRAM 和磁盘）上运行，参考了 FlexGen 的研究[sheng2023flexgen]，这有助于提升大规模模型的执行效率。 - **实现模糊语义匹配**：在 RadixAttention 中引入模糊语义匹配能力，以提高模型对上下文相似但表达不同的内容的识别能力。 - **提供更高层的编程原语**：在 SGLang 基础上提供更高层次的抽象和编程接口，使开发者能够更便捷地构建和调度复杂语言模型程序。 - **解决缓存感知调度中的饥饿问题**：当前缓存感知调度存在某些请求长期得不到响应的问题（即“饥饿”），参考了相关公平性研究[sheng2023fairness]，未来需改进调度策略以提高公平性和资源利用率。 - **增强编译器的静态优化能力**：优化 SGLang 编译器，使其能够进行更高级的静态优化，包括任务调度和内存规划，从而提升执行效率。 ### 结论 本文介绍了 **SGLang**，这是一个用于高效编程和执行结构化语言模型程序的框架。SGLang 通过引入创新的优化技术（如 **RadixAttention**、压缩有限状态机和语言解释器）显著提升了复杂语言模型程序的吞吐量与延迟表现。它为高级提示技术和智能代理工作流的开发提供了有力工具。目前，SGLang 的源码已公开，可供研究和应用。 ## Acknowledgement 该章节主要对项目的支持单位和个人表示感谢。 - **项目资助**：本项目得到了 **斯坦福大学自动推理中心**（Stanford Center for Automated Reasoning）以及多家企业的资助，包括 **Astronomer、Google、IBM、Intel、Lacework、Microsoft、Mohamed Bin Zayed人工智能大学、Nexla、Samsung SDS、Uber 和 VMware**。这些支持为项目的开展提供了重要的资源。 - **个人资助**：其中，**Lianmin Zheng** 的研究得到了 **Meta 公司的博士奖学金**（Meta Ph.D. Fellowship）的支持，体现了其个人研究的重要价值。 - **技术支持**：作者特别感谢 **Yuanhan Zhang 和 Bo Li** 提供了对 **LLaVA-NeXT（视频）** 的支持，这对项目的某些技术实现具有关键作用。 整体来看，该章节虽然简短，但详细列出了项目的重要支持来源，突出了合作与资助的重要性。 ## Appendix A Additional Details on RadixAttention ### A.1 Background on the KV Cache 本节介绍了KV Cache（键值缓存）在大语言模型（LLM）中的背景和作用。 - **KV Cache的作用**： - LLM在推理过程中分为两个阶段：**prefill**（预填充）和**decoding**（解码）。Prefill阶段处理输入序列，decoding阶段逐字生成输出。 - 每个token的处理会生成中间张量（即KV Cache），用于后续token的自注意力计算。 - KV Cache的计算只依赖于前面的token，因此**相同前缀的多个请求可以复用KV Cache**，从而减少冗余计算。 - **KV Cache重用的挑战**： - 在实际的LLM程序中，常常需要处理多个请求或者生成多个输出，这些请求可能共享部分前缀。 - **现有的系统无法完全自动处理复杂的KV Cache共享模式**，例如树状结构共享（tree-structured sharing）。 - 图9展示了四种KV Cache共享模式，包括few-shot学习示例、多轮对话的聊天历史、多输出自一致性（self-consistency）和思维树（tree-of-thought）中的搜索历史。 ![](https://img.zhaoweiguo.com/uPic/2025/08/sdBaMW.png) Figure 9:KV cache sharing examples. Blue boxes represent shareable prompt parts, green boxes indicate non-shareable parts and yellow boxes mark non-shareable model outputs. Shareable elements include few-shot learning examples, questions in self-consistency [53], chat history in multi-turn chat, and search history in tree-of-thought [56]. - **RadixAttention的优势**： - 与现有系统不同，RadixAttention可以**在运行时自动处理所有共享模式**，无需手动干预。 --- ### A.2 Pseudocode for Cache-Aware Scheduling 本节给出了RadixAttention的缓存感知调度算法的伪代码。 - **核心思想**： - 通过**前缀匹配**（prefix matching）和**缓存状态管理**（通过radix树和内存池）来高效调度多个请求。 - **关键步骤包括**： 1. 从等待队列中获取所有请求。 2. 对每个请求进行前缀匹配，找到radix树中对应的节点。 3. 根据匹配长度对请求排序，优先处理匹配较长的请求。 4. 组合请求为一个批次，同时确保内存充足或进行缓存驱逐。 5. 运行该批次的处理，并在完成后更新缓存状态。 - **重点数据结构**： - **Radix树**（T）：用于组织和匹配请求的前缀。 - **内存池**（P）：用于管理缓存的KV Cache。 - **运行批**（B）：当前正在运行的请求组。 - **等待队列**（Q）：等待处理的请求队列。 - **总结**： - 该算法通过**动态调度和缓存优化**，使得多个共享前缀的请求可以高效运行，显著减少冗余计算。 --- ### A.3 Proof of [Theorem 3.1] 本节证明了**深度优先搜索（DFS）顺序**在缓存命中率上的最优性。 - **定理核心**： - 假设一个请求批R，构建的radix树为T。 - 对于T的每条边e，对应的KV Cache需要至少计算一次，其总计算复杂度为C。 - 证明了DFS顺序可以**最小化C**，从而**最大化缓存命中率**（cache hit rate）。 - **关键结论**： - DFS顺序下，每条边的KV Cache只计算一次。 - 缓存命中率公式为： $$ \text{cache hit rate} = 1 - \frac{C}{\sum_{r \in R} \text{number of prefill tokens in } r} $$ - 当C最小化时，缓存命中率最大，达到最优。 - **扩展：在线场景下的DFS行为**： - 在新增请求的情况下，虽然DFS顺序会被打断，但**最长共享前缀优先调度（longest-shared-prefix-first）仍能近似DFS行为**。 - 通过维护缓存状态和逐步处理子树，仍可达到良好的缓存效率。 --- ### A.4 Data-Parallel Distributed RadixAttention 本节探讨了如何将RadixAttention扩展到**数据并行**（data-parallel）的分布式设置中。 - **分布式设计**： - 每个worker维护一个**局部的子树**（sub-tree）。 - 路由器（router）维护一个**元树**（meta-tree），记录所有子树及其所在的设备。 - 新请求到达时，路由器在元树上执行前缀匹配，并根据请求与worker的亲和性（affinity）决定调度到哪个worker。 - **更新与缓存一致性**： - 各worker在处理新请求时，**独立更新自己的子树**。 - 如果发生缓存驱逐（eviction），worker将驱逐记录提交到队列，由路由器在低峰时段更新元树。 - 设计为**弱一致性缓存**，在保证效率的同时牺牲部分一致性。 - **实验与效果**： - 使用四个worker和MMLU数据集进行测试，结果显示： - **线性扩展**：随着worker数量增加，性能线性提升。 - **高缓存命中率**：几乎接近最优。 - **低开销**：由于弱一致性的设计，分布式缓存的额外开销较小。 - **未来方向**： - **调度策略优化**：探索更高级的调度策略，以平衡数据本地性和并行效率之间的权衡。 - **相关研究**：Preble的工作基于SGLang的早期版本，研究了数据并行调度。 --- ### 总结 本附录详细介绍了RadixAttention在KV Cache管理和调度方面的核心技术，包括： 1. **KV Cache共享与优化**：通过radix树结构实现高效共享，减少冗余计算。 2. **缓存感知调度算法**：实现了连续批处理与动态调度，支持复杂请求模式。 3. **理论证明**：DFS顺序最优，最长共享前缀调度可近似DFS行为。 4. **分布式扩展**：支持数据并行，通过元树和子树结构实现弱一致性缓存管理。 这些技术共同提升了大语言模型在**并发、复杂请求场景下的运行效率和资源利用率**。 ## Appendix B Additional Details on Compressed Finite State Machine ![](https://img.zhaoweiguo.com/uPic/2025/08/fOqkfh.png) Figure 10:Example of how regex is converted into FSM and how FSM guides the decoding process. 本节主要介绍压缩有限状态机的背景及其在**加速约束解码**中的实现细节。目标是使语言模型（LLM）输出的内容遵循**正则表达式（regex）**的约束，从而可以用于生成结构化数据（如 JSON 格式）。为此，作者将正则表达式转换为**有限状态机（FSM）**，并在解码过程中使用该状态机来指导生成过程 [[54]](https://arxiv.org/html/2312.07104v2#bib.bib54)。 ### FSM 的基本原理 FSM 是一种由**状态节点**和**带字符串的转移边**构成的图结构。解码过程从初始状态出发，通过选择边上的字符串逐步转移状态，直到到达**终止状态**。这个机制可以**过滤掉不符合 regex 的 token**，从而实现结构化输出。如图 10 所示，LLM 在解码过程中会根据当前 FSM 所处的状态，限制下一步可能生成的 token。 图 10 展示了 regex 转换为 FSM 的过程，并说明 FSM 如何引导解码流程。 --- ### 挑战：字符串与 token 的映射问题 正则表达式是基于字符串的，而 LLM 是基于 token 的，因此存在**字符串与 token 之间缺乏一一对应**的问题，导致约束解码复杂化。这也是压缩有限状态机设计的一个核心挑战。 --- 本节内容改编自一篇早期博客[[333]](https://lmsys.org/blog/2024-02-05-compressed-fsm/)，建议读者阅读以获得更深入的背景知识。 --- ### B.1 压缩有限状态机的实现细节 为了简化压缩 FSM 的构建，作者首先基于**字符/字符串**构建原始 FSM，而非直接基于 token。这一步骤为后续的压缩奠定了基础。 #### 关键概念定义： - **Singular transition edge（单向转移边）**：如果一个边的**起点节点只有一个后续节点**，并且该边**只接受一个特定的字符/字符串**，则称为单向边。 - **Compressed edge（压缩边）**：当多个连续的单向边可以被压缩为一个边时，其文本为这些边文本的拼接。压缩直到无法进一步压缩为止。 通过递归地将单向边合并到其前边中，最终获得一个压缩后的 FSM。这种方式能显著**提升解码效率**，如图 11 所示，展示了压缩 FSM 相比于普通 FSM 在运行效率上的提升。 图 11 对比了压缩 FSM 与普通 FSM 的解码过程，左侧显示每个前向传播的解码过程，右侧解释了结果的构成来源。 ![](https://img.zhaoweiguo.com/uPic/2025/08/SFJB5E.png) Figure 11:Comparison of decoding using Compressed FSM versus normal FSM: The left subfigure depicts the decoding process per forward pass, while the right subfigure explains the origins of various result components. --- ### B.2 通过重分词处理 token 化伪影（Retokenization） 在生成一个新 token 后，系统会获取其对应的字符串，并在当前状态的所有出边中查找匹配的边。若该边是压缩边（包含较长的字符串），则可以**提前预测后续的 token 内容**，这种机制称为**Jump Forward（跳跃前进）**，从而加速解码。 但由于 LLM 的 token 化方式与直接字符串分割不同，直接分割字符串可能会破坏语义。例如，压缩字符串 `{"summary":` 可能被正确 token 化为 `{", summary, ":`，而非错误地拆分为 `{", summa, ry, ...`。 为解决这个问题，系统在处理压缩边时，使用**原始 tokenizer** 对**整个压缩边文本**进行重分词，确保与 LLM 的输入格式一致。该步骤带来的额外开销较小。 --- ### B.3 未来扩展：处理概率分布失真问题 由于字符串与 token 之间的映射问题，可能导致**概率分布的扭曲** [[50]](https://arxiv.org/html/2312.07104v2#bib.bib50)。例如，一个压缩边可能将多个可能的 token 序列映射到同一个选项，而模型可能会错误地选择概率最高的那个，从而导致语义不一致。 例如，正则表达式 `[ABCD][+-]?` 用于表示 A+ 到 D- 的成绩，但若将其替换为 `Excellent|Above Average|Fair|Below Average`，模型可能错误地将 "A" 映射为 "Above Average"，因为后者在压缩边中出现，导致**等级排序混乱**。 解决方法之一是**在预填充提示（prefill prompt）中加入选项或 regex**，引导模型生成正确的 token 序列。但这种方法仅是表面解决，**无法从根本上解决概率失真问题**。因此，作者指出这一方向仍需进一步研究，以提升压缩 FSM 的准确性。 --- ### 总结 本节详细介绍了压缩有限状态机（Compressed FSM）在约束解码中的实现机制，包括： - 将 regex 转换为 FSM，并用于控制解码流程； - 通过**压缩 FSM** 提升解码效率； - 通过**重分词**处理 token 化的不一致性； - 指出未来需要解决的**概率分布扭曲**问题。 整体来看，压缩 FSM 是实现结构化输出的一个关键技术，但其在 token 化和概率建模方面仍面临挑战，需要进一步研究与优化。 ## Appendix C Additional Experimental Setups and Results ### 其他实验设置 本部分介绍了一些额外实验的硬件配置与模型运行情况： - **图5** 和 **图6** 的实验是在单块 A10G（24GB）GPU 上运行 Llama-7B 模型获得的。 - **图7** 的实验是在 8 块 A10G（24GB）GPU 上使用 **张量并行（Tensor Parallelism）** 技术运行 Mixtral-8x7B 模型获得的。 - **图8(c)** 的实验同样是在单块 A10G（24GB）GPU 上运行 Llama-7B 模型。 - **图12** 的实验是在 4 块 A100G（80GB）GPU 上运行 Llama-70B 模型，同样使用了张量并行。 - **表2** 中的实验分别在单块 A10G（24GB）GPU 上运行 LLaVA-v1.5-7B 模型，以及在单块 A100G（80GB）GPU 上运行 LLaVA-Next-34B 模型。 > ⚠️ 注：每个基准测试图中的柱状图需要运行数分钟到一小时不等，说明实验耗时较长，对硬件设备要求较高。 --- ### 其他实验结果 - **图13** 展示了在不同基准测试中，**实际缓存命中率** 与 **理想缓存命中率** 的对比，用于评估缓存效率。 - **图12（如图 x12 所示）** 展示了在使用张量并行技术运行 Llama-2-70B 模型时的**吞吐量（throughput）**。该图显示了不同配置下的性能表现，**值越高越好**。 > ✅ **重点内容**：图12 和 图13 是关键的性能评估图。图12 用于评估大规模模型在并行计算下的吞吐性能，图13 用于评估缓存机制的优化效果。 --- ### SGLang 程序与数据流图（图14） ![](https://img.zhaoweiguo.com/uPic/2025/08/KlfFN4.jpg) Figure 14: An SGLang program and its corresponding dataflow graph. 图14 包含两部分内容： - **图14(a)** 展示了一个 SGLang 程序，用于并行提示建议（tip suggestion）任务，使用了骨架思维提示（skeleton-of-thought prompting）的方法。 - **图14(b)** 展示了上述程序的**计算图（数据流图）**，其中三个流（stream）分别对应三个函数调用，体现了程序的结构化执行流程。 > ✅ **重点内容**：这部分展示了 SGLang 的结构化执行特性，通过数据流图清晰展示了并行与函数调用之间的关系，是理解 SGLang 执行机制的重要部分。 ## Appendix D Compiler Mode ## Appendix D 编译器模式 除了论文主体中使用的解释器模式，SGLang 程序还可以通过编译为**计算图**并在图执行器中运行。这种方式为**更多的编译优化**提供了可能，例如对图进行重写和进行更静态的规划。 --- ### D.1 设计与实现 本节介绍了为 SGLang 设计的**中间表示（IR）**，它将 SGLang 程序的结构和操作表示为一个计算图。该图包括**操作符节点**和**依赖关系边**，用于表示程序中的结构和执行顺序。 - **节点类型**包括：`ConstantText`（常量文本）、`Argument`（参数）、`Gen`（生成）、`Select`（选择）、`Variable`（变量）、`Fork`（分叉）、`GetForkItem`（获取分叉项）、`Join`（合并）等。 - **依赖关系**分为两类： - **流内依赖（intra-stream）**：同一流中通过 `+=` 提交的操作必须按顺序执行。 - **流间依赖（inter-stream）**：当一个流需要从另一个流获取变量值时，必须进行同步。 - **图生成方式**通过**追踪（tracing）**运行程序，使用抽象参数动态构建图。这种方式**不适用于包含数据依赖控制流的程序**，这是未来需要解决的问题。 - 一旦图构建完成，即可通过图执行器运行，无需重新解释原始 Python 程序。这带来了**图重写优化、运行时开销降低和程序序列化**等优势。 - 执行时，为每个数据流启动一个**流执行器**，根据拓扑顺序将 IR 节点分发到流中。 --- ### D.2 编译优化案例研究：代码移动以提高前缀共享 本节探讨了一种针对 SGLang IR 的**编译优化技术**：通过**代码移动**来**提高前缀共享**。这种优化通过**调整图中节点顺序**，来**延长可共享的文本前缀长度**。这种优化属于**激进类型**，因为它**不严格保持原计算顺序**。 - **优化示例**：将提示语从 “Here is a question + {question}. Please act as a math expert...” 重写为 “Please act as a math expert... Here is a question + {question}.”，从而使得前缀更长、共享更好。 - **优化实现方式**：由于传统程序分析方法难以处理自然语言，我们**使用 GPT-4** 来对图节点进行重新排序。 - **实验设计**：收集了 20 个提示模板，其中 5 个作为示例，其余 15 个作为测试用例。 - **优化效果**：在 15 个测试模板中，GPT-4 成功对 12 个进行了无语义变化的重排序，平均**前缀共享长度增加了 60 个 token**。 - **失败原因**：部分失败是由于 GPT-4 对图节点的语义理解不准确，导致错误地将所有常量前置，改变了原义。 - **研究意义**：本案例探讨了**使用 GPT-4 实现编译器优化的可行性**，但指出未来仍需进一步提高这类优化的**可靠性**。 --- ### 总结 - **编译器模式**为 SGLang 提供了性能优化的新方向：通过图执行器执行程序，带来更高效、更灵活的执行方式。 - **中间表示（IR）**的设计是关键，它支持节点依赖分析、图重写等高级编译优化。 - **代码移动优化**展示了如何利用 LLM（如 GPT-4）实现自然语言控制流的优化，这是传统编译器难以处理的问题。 - **未来工作**包括支持数据依赖控制流、提高 GPT 类模型在编译优化中的可靠性等。 --- 以上是对 Appendix D 内容的结构化总结，重点强调了 IR 设计、图执行机制、代码移动优化方法及其实验结果。