SageSched: Efficient LLM Scheduling Confronting Demand Uncertainty and Hybridity

SageSched 是一种高效的 LLM 调度器，它通过结合提示内容与历史结果来预测输出长度分布，并综合考虑计算与内存成本，利用不确定性感知策略在需求不确定和混合负载场景下实现了超过 28.7% 的效率提升。

要点

这篇论文介绍了一个名为 SageSched 的新系统，它的任务是让大型语言模型（LLM，比如我们聊天用的 AI）在同时处理大量请求时，运行得更快、更顺畅。

为了让你轻松理解，我们可以把 AI 服务器 想象成一家繁忙的“魔法面包店”，而 AI 模型 就是面包师。

1. 面包店遇到了什么麻烦？（核心问题）

这家面包店现在生意太火爆了，但有两个大难题：

• 难题一：不知道要烤多久（需求的不确定性）

  • 现状：顾客（用户）点单时，只说“我要一个面包”，但没说具体要多大。面包师开始烤了，可能烤 3 分钟就出炉，也可能烤了 30 分钟还在烤。
  • 后果：传统的排队系统（比如“先来先服务”）不管这个。如果第一个顾客点了一个巨无霸面包，后面排队的 10 个只想吃小面包的顾客都得干等着，大家都急得跳脚。
  • 比喻：就像你在餐厅点菜，前面的人点了个需要炖 3 小时的佛跳墙，后面点炒青菜的人只能饿着肚子等，这体验太糟糕了。

• 难题二：既要火又要锅（资源的混合性）

  • 现状：烤面包不仅需要火（计算能力，GPU 算力），还需要大烤盘（显存，KVCache）。
  • 后果：以前的系统只关心“火”够不够大，却忽略了“烤盘”够不够大。有时候，一个面包虽然烤得快（火够大），但它占用了巨大的烤盘，导致后面很多小面包根本放不进去。
  • 比喻：就像出租车调度，以前只考虑“司机开得快不快”，却不管“车座够不够坐”。如果一辆大车只坐一个人，后面很多想拼车的人就坐不上了。

2. SageSched 是怎么解决的？（三大法宝）

SageSched 就像给面包店请了一位超级聪明的店长，他有三招绝活：

第一招：看人下菜碟的“预言家”（语义感知历史预测）

• 传统做法：请一个专门的“算命先生”（复杂的 AI 模型）来猜面包要烤多久。这太慢了，而且算得不准，换个面包师（模型）还得重新请人。
• SageSched 的做法：店长翻开过去的账本。
  • 他发现：“哦，刚才那个顾客问‘写一首关于春天的诗’，烤了 5 分钟；现在这个顾客也问‘写一首关于春天的诗’，那大概率也要 5 分钟。”
  • 他不仅猜时间，还能猜出时间的范围（比如：有 80% 概率是 4-6 分钟，20% 概率是 10 分钟）。
  • 比喻：就像老练的厨师，不用拿计算器，看一眼菜单就知道这道菜大概要多久，而且心里清楚这道菜可能快也可能慢，留有余地。

第二招：算总账的“精算师”（基于资源边界的成本建模）

• 传统做法：只算“烤了多久”（计算时间）。
• SageSched 的做法：店长会算一笔总账：烤的时间 + 占用的烤盘大小。
  • 如果一个面包烤得很快，但占用了整个大烤盘，导致后面 10 个小面包没地方放，那这个面包的“真实成本”其实很高。
  • 他建立了一个统一的公式，把“火”和“锅”的消耗都算进去，给每个订单打个真实分数。
  • 比喻：就像打车软件，不仅看路程长短，还看这辆车是不是把整条路都堵死了。如果一辆大车只坐一个人却堵了路，它的“打车成本”其实比坐满人的小车要高。

第三招：会变通的“调度大师”（不确定性感知调度）

• 传统做法：谁时间短谁先上（最短作业优先）。但这有个问题：如果两个面包，一个确定烤 5 分钟，另一个不确定（可能 1 分钟，也可能 100 分钟），选哪个？
• SageSched 的做法：使用一种叫 Gittins 指数 的数学魔法。
  • 它不只看“平均时间”，而是看“谁最有可能马上做完”。
  • 它还会动态调整：如果一个正在烤的面包突然变慢了，店长会立刻重新计算它的优先级，把它插队或者换位置，确保大家都能尽快吃上。
  • 比喻：就像机场安检，如果前面那个人证件齐全但动作慢，后面有个证件不全但马上能补好的，聪明的安检员会灵活处理，让整体队伍流动得最快，而不是死板地按顺序来。

3. 效果如何？

经过在真实服务器上的测试，SageSched 就像给面包店装上了涡轮增压：

• 效率提升：相比目前最先进的系统，它让所有顾客平均等待时间缩短了 28.7%。
• 更稳定：即使面对各种奇怪的订单（有的长、有的短、有的占地方），它也能保持队伍不乱。

总结

SageSched 就是一个懂历史、会算账、能变通的 AI 调度员。它不再盲目地让 AI 模型排队，而是通过参考历史经验、计算真实资源消耗、以及灵活调整顺序，让每一个 AI 请求都能以最快速度得到响应，极大地提升了我们使用 AI 时的体验。

简单来说，它让 AI 服务器从“死板的流水线”变成了“灵活的智能管家”。

技术摘要

以下是关于论文《SageSched: Efficient LLM Scheduling Confronting Demand Uncertainty and Hybridity》（SageSched：应对需求不确定性与混合性的高效大语言模型调度）的详细技术总结。

1. 研究背景与问题定义

随着大语言模型（LLM）的广泛应用，如何在 GPU 服务器上高效调度并发推理请求成为提升用户体验的关键。现有的 LLM 调度器（如 vLLM 的 FCFS 策略或基于预测的 SJF 策略）在面对 LLM 推理的两个核心特性时表现不佳：

• 需求不确定性 (Demand Uncertainty)：由于 LLM 的自回归生成特性，输出 Token 的长度在推理开始前是未知的（非确定性）。现有方法通常依赖微调模型预测单一的长度值，这不仅训练成本高，且难以准确捕捉真实的概率分布，导致调度决策次优。
• 需求混合性 (Demand Hybridity)：LLM 推理既消耗计算资源（Compute-intensive），也严重依赖显存（Memory-intensive，特别是 KVCache）。现有调度器往往仅关注计算时间（输出长度），忽略了显存占用对并发能力的限制。在显存瓶颈下，单纯按输出长度排序可能导致调度效率低下。

核心问题：现有的调度策略未能同时有效处理“输出长度的不确定性分布”和“计算与显存的混合资源竞争”，导致端到端的最后一个 Token 到达时间 (TTLT) 较高。

2. 方法论：SageSched 设计

SageSched 是一个针对 LLM 工作负载特性设计的新型调度器，包含三个核心技术模块：

2.1 语义感知的基于历史的预测器 (Semantic-aware History-based Predictor)

• 动机：直接微调模型预测分布成本高且不准确。研究发现，提示词（Prompt）的语义相似度与输出长度分布高度相关。
• 机制：
  • 不训练任何预测模型，而是维护一个最近服务的请求历史库（记录 Prompt 内容和输出长度分布）。
  • 对于新请求，计算其 Prompt 与历史请求的语义相似度（通过 Embedding 余弦相似度）。
  • 筛选出高相似度的历史请求，将其输出长度分布直接作为新请求的预测分布。
• 优势：无需训练（Training-free），轻量级（<0.5ms/请求），且能直接输出概率分布而非单一数值。

2.2 基于资源边界的成本建模 (Resource-bound-based Cost Modeling)

• 动机：传统的“输出长度”无法准确代表服务成本，因为显存瓶颈（KVCache）和计算瓶颈下的成本模型不同。
• 机制：
  • 分析发现，无论是显存受限（Memory-bound）还是计算受限（Compute-bound）场景，服务成本 $C$ 都可以统一建模为输入长度 $I$ 和输出长度 $O$ 的函数：
    $$C = \frac{O^2}{2} + I \times O$$
  • 该公式推导自 KVCache 的累积占用（显存）和注意力机制的计算量（计算），统一了两种资源视角的成本度量。
• 优势：能够准确捕捉请求在混合资源约束下的真实服务代价，避免了仅考虑计算时间的偏差。

2.3 不确定性感知的调度策略 (Uncertainty-aware Scheduling Policy)

• 动机：由于输出长度是概率分布，使用期望值（Mean）作为调度指标并非最优解（如图 6 所示，某些长尾分布的请求若优先处理可能降低整体延迟）。
• 机制：
  • 引入 Gittins Index（吉廷斯指数） 策略。将每个请求视为一个多臂老虎机问题，Gittins 指数定义为在给定服务预算下，单位成功概率的最小摊销成本。
  • 动态刷新：为了平衡调度时效性与系统稳定性，将请求的成本范围划分为多个桶（Bucket），仅在跨越桶边界时重新计算并刷新 Gittins 指数，而非每一步都刷新。
• 优势：理论上证明了基于 Gittins 指数的调度能在已知分布但未知具体时长的情况下，最小化平均延迟（TTLT）。

3. 实验结果

作者在 vLLM 框架上实现了 SageSched，并在多种真实数据集（SharedGPT, Alpaca, Document-Write）和不同模型（Llama3.1-8B, Qwen3-32B）及硬件（A40, H800）上进行了评估。

• 端到端性能：
  • 在混合数据集测试中，SageSched 相比次优的调度器（TRAIL）在平均 TTLT 上提升了 28.7%。
  • 在高并发场景下（如 8 RPS），性能提升更为显著。
  • 在 TTFT（首 Token 延迟）方面，SageSched 也表现优异，有效缓解了队头阻塞（Head-of-Line Blocking）问题。
• 组件有效性分析：
  • 预测器：语义感知的历史预测器在精度和开销上均优于基于 LLM 微调的预测器。
  • 成本模型：基于资源边界的成本模型比单纯基于输出长度或输入输出加权和的模型更优。
  • 调度策略：基于 Gittins 指数的排序及动态刷新机制显著优于基于均值（Mean）的排序，且在预测存在噪声时表现出更强的鲁棒性。
• 可扩展性：
  • 在模拟的 64 节点集群中，SageSched 的调度开销随规模线性增长，但在最大规模下，每个请求的额外延迟仅约 100ms，相对于秒级/分钟级的推理任务可忽略不计。

4. 主要贡献

1. 问题识别：通过测试床测量，明确指出了现有调度器在处理 LLM 工作负载的“不确定性”和“混合性”时的局限性。
2. 系统创新：提出了 SageSched，集成了三项关键技术：
   • 轻量级、高精度的语义感知历史预测器（输出分布而非单点值）。
   • 统一计算与显存视角的资源边界成本模型。
   • 基于Gittins 指数的不确定性感知调度算法。
3. 性能突破：通过实验和模拟验证，SageSched 能显著降低平均 TTLT（提升超过 28.7%），并在大规模集群中保持低开销。

5. 意义与价值

• 理论价值：首次将 Gittins 策略引入 LLM 调度领域，解决了在需求分布已知但具体时长未知情况下的最优调度问题，为处理不确定性工作负载提供了新的理论视角。
• 工程价值：SageSched 无需重新训练模型，直接基于历史数据运行，易于集成到现有的 LLM 推理框架（如 vLLM）中。它解决了当前 LLM 服务中显存与计算资源竞争导致的效率瓶颈，对于提升高并发场景下的用户体验（降低等待时间）具有重要意义。
• 通用性：该方法不仅适用于当前的 LLM，其处理“不确定性”和“混合资源约束”的思路也可推广至其他具有类似特性的 AI 推理或计算任务。

总结而言，SageSched 通过精准建模 LLM 推理的不确定性和资源混合特性，利用分布预测和最优调度理论，实现了显著的性能提升，是 LLM 服务调度领域的一项重要进展。