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

复合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获得分布便可以直接用于计算调度每个节点的熵减，无需额外的测量。

实验结果：平均任务完成时间最低降至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

文章来自公众号“量子位”，作者“LLMSched团队”