提速 79%！上交大新方法优化企业级 AI 流程调度

复合 LLM 应用 ( compound LLM applications ) 是一种结合大语言模型（LLM）与外部工具、API、或其他 LLM 的高效多阶段工作流应用。

前，服务这些应任务需要对运时不确定、作流结构不确定等问题，这对现有集群任务调度算法提出了极大挑战，并严重影响任务运效率。

为了解决上述问题，上海交通大学朱怡飞教授团队联合江行智能提出调度框架 LLMSched，通过引入三类新节点来扩展传统任务表征方法实现复合 LLM 应用任务的有效表征，借助贝叶斯网络识别可降低不确定性的关键节点，并以信息熵衡量节点的熵减程度。

目前论文已被 IEEE ICDCS ’ 25 接收。

实验结果显示，LLMSched 结合探索 - 利用策略来平衡调度不确定性与当前调度收益，最终实现高效调度复合 LLM 应用，相较现有调度器平均任务完成时间降低 14~79%。

LLMSched：DAG 模型重构 + 熵减调度

团队通过对现有复合 LLM 应用的设计分析与实验，总结出复合 LLM 应用以下两点不确定性：

时长不确定性：单任务耗时波动高达 300 秒（图 1a）。该不确定性主要来源于 LLM 的自回归生成特性。

结构不确定性：任务步骤数与运行结构随机波动（图 1b/c）。该不确定性主要来源于 LLM 在复合 LLM 应用中发挥的决策与规划功能。

复合 LLM 应用这两种不确定性极大限制了传统调度的性能表现。如下图实例所示，传统最短任务优先 ( Shortest Job First ) 调度因误判耗时导致效率低下 ( 任务平均完成时间 6.5s ) ，而不确定性感知的调度器通过提前执行高熵减阶段（TA-1）降低不确定性，从而达到更有效调度 ( 任务平均完成时间 5s ) 。

DAG 模型重构：调度的基石

为了应对复合 LLM 应用中存在的结构不确定性，研究团队提出全新有向无环图（DAG）建模框架，如下图所示。该框架引入了三种节点，常规节点（Regular Stage），LLM 节点（LLM Stage）与动态虚拟节点（Dynamic Stage）。其中，常规节点对应外部工具、api 等的调用，LLM 节点对应 LLM 推理任务，动态虚拟节点对应由 LLM 规划生成的子 DAG。

重构后的 DAG 模型能将现有的复合 LLM 应用表征为拥有固定拓扑结构的调度单元，为之后的调度设计建立了基础。

贝叶斯分析器 + 熵减衡量机制：让系统越算越 " 清醒 "

团队在研究过程中意识到复合 LLM 应用的部分节点存在显著的关联性。这种关联性使得在执行完成某些前置节点后，后续节点的不确定性能够有效降低，具体表现如下：

1、规划式任务中 LLM 规划节点后的工作流完全由该节点决定。完成该 LLM 规划节点后，所规划的子工作流的未知拓扑结构可被完全揭示。

2、相当一部分的节点在运行时长上存在较高的关联性（下图所示）。在完成前置节点后，后续节点的时长不确定性进一步降低。具体表现在后续节点的运行时长的条件分布更为紧凑、可预测。

为此，团队为每个应用在对应数据集上收集了大量的运行时长数据，并在数据上基于重构的 DAG 模型训练贝叶斯网络（BN）来获取节点的运行时长分布与节点之间的关联性。当 BN 中的一个节点存在一条或多条出边时，该节点便与其他的节点存在关联，调度该节点便可以降低其他节点的不确定性。

考虑到实际情况中，不同的节点能够降低的不确定性程度大不相同，团队引入信息论中信息熵的概念，使用互信息衡量，如下图所示。由于信息熵与互信息均通过变量的分布进行计算，因此之前通过 BN 获得分布便可以直接用于计算调度每个节点的熵减，无需额外的测量。

为了将上述的熵减思想用于优化任务的平均完成时间，团队使用 ε -greedy 算法结合最短剩余时间优先与最大熵减优先两种策略，提出了一个高效的调度算法。该算法借鉴了探索 - 利用的思想，巧妙地在降低任务不确定性与降低任务完成时间两个潜在的冲突目标中达到了平衡。在调度过程中，调度算法会收集任务完成的时长信息，利用贝叶斯网络动态更新每个任务的运行时长，从而获取更精确的任务时长估计。该算法的复杂度仅为，能够对动态的负载做出快速的调度决策。

实验结果：平均任务完成时间最低降至 79%

团队选取了六种代表性的复合 LLM 应用，并基于此构建了 4 种不同应用组成的负载，如下图所示。团队在一台搭载 H800 GPU 的 ubuntu 机器上使用 vLLM 框架与 LLaMA-7B 模型进行了实验。

实验结果表明，LLMSched 相较于现有的调度器最多可降低 79% 的平均任务完成时间。

为了进一步衡量 LLMSched 的可拓展性与适应性，团队构建了一个简易的 LLM 推理模拟器，并在上面进行了多组不同任务数量的实验。如下图所示，团队展示了不同任务数量的仿真结果。

实验结果表明，LLMSched 在任意一组实验设置上均取得领先的成绩，同时随着任务数量增加，LLMSched 的优势变得更为突出，比如，与 Decima 相比，在包含 100、200、300 和 400 个任务的混合工作负载中，LLMSched 分别降低了 38%、65%、73% 和 75% 的平均 JCT，这展示了 LLMSched 的可扩展性。

此外，团队在测试平台实验中，在下图中展示了每种方法的平均调度开销（总开销除以每种方法的调用次数，包括 BN 推理和熵计算）。团队方法的平均调度开销略高于 FCFS、SJF 和 Fair 等简单启发式算法，但远低于 Decima 和 Carbyne 这两种复杂方法。此外，LLMSched 的平均开销对于所有类型的工作负载都低于 3 毫秒，这表明 LLMSched 可以在不影响平均 JCT 的情况下执行高效的实时调度。

消融研究

为了分析这两个组件的有效性，团队进行了消融研究，创建了两种额外的方法——LLMSched w/o BN 和 LLMSched w/o uncertainty。第一种方法遵循算法 1 中提出的相同调度方案，但使用历史任务平均持续时间进行估计。第二种方法使用贝叶斯网络更新任务持续时间的后验分布，但仅执行 SRTF 策略。

上图展示了在四种类型工作负载上进行的消融研究结果。团队将两种方法的平均 JCT 归一化到 LLMSched 的水平。

对于 LLMSched w/o BN，在四种类型工作负载上，平均 JCT 分别比 LLMSched 高 18%、17%、20% 和 5%。这表明 BN 发挥了重要作用，因为它显著提高了任务持续时间估计的准确性。借助 BN，可以通过利用阶段间相关性，更动态地更新和更准确地预测非计划阶段的任务持续时间。

对于 LLMSched w/o uncertainty，在四种类型工作负载上，平均 JCT 分别比 LLMSched 高 21%、12%、15% 和 13%。这表明不确定性感知策略在有效引导探索过程中至关重要。当处理混合工作负载时，其重要性尤为突出，因为各阶段的不确定性减少差异显著。对于这种工作负载，LLMSched w/o BN 的性能优于 LLMSched w/o uncertainty。

LLMSched 为 LLM 服务优化开辟了新方向，尤其对多模块协作的 Agent 系统、LLM 推理集群资源调度具有重要参考价值。其不确定性量化框架可扩展至其他动态任务场景，推动智能调度理论与实际系统的深度融合。

论文链接：https://arxiv.org/abs/2504.03444

一键三连「点赞」「转发」「小心心」

欢迎在评论区留下你的想法！

— 完 —

点亮星标

科技前沿进展每日见