TOPAS：面向工作流的多智能体LLM服务前缀状态调度

# TOPAS：面向多智能体大语言模型服务的流程感知前缀状态调度
来源：https://arxiv.org/html/2608.25523
Hongqiu Ni1，Han Tian1，Chi Zhang2，Guopeng Li1，Haisheng Tan1
所属机构：1 中国科学技术大学，中国；2 合肥工业大学，中国

###### 摘要

前缀缓存为多智能体大语言模型（LLM）服务引入了一个根本性权衡：为智能体保留一个长系统提示词键值（KV）缓存可以加速后续调用，但却减少了可用于批处理并发请求的GPU内存。在多阶段工作流中，现有调度器往往要么优先考虑即时的前缀局部性，要么优先考虑整体工作流进度。然而，在共享的KV缓存预算下，单独优化任一目标都可能因下游延迟或频繁的前缀替换而延长任务级作业完成时间（JCT）。为了取得平衡，本文提出了**TOPAS**（面向任务的前缀感知调度器），它能联合决策哪些智能体前缀保留在缓存中以及哪些请求被调度执行。TOPAS通过权衡每个任务最长剩余服务路径的预期缩短与前缀移动和抢占的短期成本，在考虑前缀复用收益的前提下，对候选的决策后状态进行评分。此外，还引入了一个任务级老化机制以防止饥饿现象。

我们在SGLang框架中实现了TOPAS，并在三个合成有向无环图（DAG）工作负载和两个MetaGPT软件开发工作流上评估了其性能。与针对每种工作负载和指标的最佳基线相比，在合成工作负载上，TOPAS将平均/p99 JCT最多降低了39.8%/49.4%；在MetaGPT-SOP上平均JCT降低了9.8%；在MetaGPT-TL上平均/p99 JCT分别降低了22.0%/26.6%。

## I 引言

多智能体LLM应用通过由角色专精的智能体生成的相互依赖的请求来处理复杂任务\[32 (https://arxiv.org/html/2608.25523#bib.bib12), 20 (https://arxiv.org/html/2608.25523#bib.bib38)\]。每个请求包含一个智能体特定的静态前缀，其KV缓存可以在不同任务中同一智能体的请求间复用。SGLang等服务系统在基数树中维护缓存的KV对，共享相同智能体前缀的请求会遍历相同的静态路径，并各自附加其请求特定的动态内容。将此缓保留在GPU内存中——称为*前缀常驻*——消除了冗余的预填充计算，但会与并发执行的请求竞争有限的KV预算。长系统提示进一步放大了复用收益和常驻成本。因此，请求调度不仅影响任务进度，也影响GPU的整体服务能力。

SGLang等主流推理框架侧重于优化批处理、前缀缓存和KV缓存管理\[11 (https://arxiv.org/html/2608.25523#bib.bib1), 37 (https://arxiv.org/html/2608.25523#bib.bib3)\]。它们的调度器主要在请求层面运行，使用引擎本地信息对就绪请求进行排序。虽然非常适合每次请求的执行优化，但这种请求级视角仅间接反映了编排层所监控的请求间依赖关系和程序级进度。

近期努力旨在通过不同策略弥合这一抽象差距。Parrot和Autellix将应用数据流或程序级进度纳入请求调度\[13 (https://arxiv.org/html/2608.25523#bib.bib4), 16 (https://arxiv.org/html/2608.25523#bib.bib6)\]，而KVFlow则利用工作流上下文进行前缀缓存放置\[18 (https://arxiv.org/html/2608.25523#bib.bib14)\]。这些系统主要优化应用进度、缓存可用性或资源放置，而前缀常驻与请求准入基本是分离的。这种解耦可能导致异构前缀共存于缓存中——减少了可行的并发批大小——或在执行切换到不同智能体时引发频繁的前缀逐出和重载。

端到端进度与前缀复用之间存在固有冲突。合并来自同一智能体的请求允许更少的常驻前缀支持更大的批，但这可能在下游任务待处理时阻碍上游执行。相反，优先考虑工作流进度往往会触发频繁的智能体切换，牺牲复用并产生显著的前缀移动开销。因此，调度器必须协调前缀局部性与整体进度，而不是单独优化任一目标。

因此，我们提出以下问题：**在受限的GPU内存预算下，服务系统如何在整个工作流执行过程中协调前缀常驻和请求准入，以最小化*任务级*作业完成时间（JCT）？** 我们将此问题形式化为*在线前缀状态调度*。在每个调度点，调度器联合决策保留哪些智能体前缀以及接纳哪些就绪请求，受共享KV缓存预算约束。这一联合决策决定了当前的批容量、即时的任务进度，以及最有可能被后续工作流步骤复用的前缀集合。

为解决此问题，我们提出了**TOPAS**，一个面向任务的前缀感知调度器，其关键创新在于将前缀常驻视为一个显式的工作流级调度决策，与请求准入联合优化，而非作为请求排序和缓存逐出的间接副产品。据我们所知，TOPAS是首个在共享KV预算下联合优化前缀常驻和请求准入以降低任务级JCT的多智能体LLM调度器。TOPAS执行分层搜索以构建决策后的GPU状态，每个状态指定一个常驻前缀集和一个兼容的已接纳请求分配。它通过一个JCT导向的效用函数选择最优状态，该效用函数权衡了每个任务最长剩余服务路径的预期缩短与前缀复用的短期收益，并考虑了前缀移动和抢占的成本。

我们的贡献总结如下：
- •我们形式化了在线前缀状态调度问题，该问题在共享KV缓存预算下联合选择常驻智能体前缀和接纳请求。我们的诊断分析揭示，异构前缀共存会减少动态批容量，而“局部性优先”和“进度优先”策略无法互补，导致性能不佳。
- •我们引入了TOPAS，一种在线调度器，通过JCT导向的效用函数联合确定前缀常驻和请求准入。该效用函数平衡了任务最长剩余服务路径的预期缩短与前缀复用的短期收益。并引入了任务级老化机制以防止饥饿。
- •我们在SGLang上实现了TOPAS，并在三个合成DAG工作负载和两个MetaGPT工作负载上进行了评估。与每种工作负载和指标下的最佳基线相比，TOPAS在合成工作负载上将平均/p99 JCT最多降低了39.8%/49.4%；在MetaGPT-SOP上平均JCT降低了9.8%；在MetaGPT-TL上平均和p99 JCT分别降低了22.0%和26.6%。

## II 动机：进度-复用冲突

任务级策略可以利用工作流依赖关系来决定哪些任务或阶段应该推进，但它们的决策最终由请求级服务引擎执行。该引擎在有限的KV预算下，不断将就绪请求接纳到连续批处理中。同一智能体的请求复用常驻的静态前缀缓存，而每个请求为动态后缀和解码令牌消耗额外的KV容量。因此，接纳顺序和缓存逐出决定了哪些前缀保持常驻以及多少请求可以一起运行。仅靠任务级优先级无法控制这种前缀-批交互；以下诊断分析隔离了其两个后果。

为了研究请求顺序如何影响批处理，我们在原生LLM服务运行时上使用了一个包含两个智能体的微基准测试。该工作负载包含每个智能体A和B的n个独立请求。智能体具有不同的长前缀，而所有请求使用相同的动态后缀和解码长度。交替顺序（A, B, A, B, ...）在整个运行期间保持两个前缀常驻，而分组顺序（Grouped）则将每个智能体的请求集中服务。两种顺序包含相同的请求并使用相同的KV预算；仅顺序不同。

表I：在FCFS下，异构前缀共存会缩减运行批大小，从而增加总时间。斜杠分隔的值为分组顺序/交替顺序。
表I (https://arxiv.org/html/2608.25523#S2.T1)显示，分组顺序使平均运行批大小翻倍；交替顺序完成工作负载的时间是其1.8–1.9倍。将同一智能体的请求放在一起服务，可以让一个常驻前缀支持更大的批。而在智能体之间交替则将KV容量分配给两个长前缀，留给动态后缀和解码令牌的空间更少。

诊断1中的批处理效益暗示了一种自然的应对方式：优先处理可以复用常驻前缀的请求。最长前缀匹配（LPM）是一种代表性的局部性优先策略：它优先处理具有最长即时可复用前缀的就绪请求。但它并不主动选择目标前缀状态。它以反应式、到达驱动的方式运行：请求顺序和缓存逐出决定了前缀常驻，而这又成为下一个决策的局部性信号。在一个A→B→C的工作流中，如果请求持续到达A，这种反馈循环会将服务停留在工作流入口附近，延迟B和C阶段。为了测试主动控制是否能打破这种行为，我们在LPM上添加了一个简单的下游门控机制，一旦C的积压增加就优先处理C。图1 (https://arxiv.org/html/2608.25523#S2.F1)显示，这种粗略干预取得了比LPM更低的平均JCT。

进度优先调度是另一个极端。最短剩余处理时间（SRPT）优先处理剩余处理时间较短的任务，可以将其推向工作流出口。但它没有前缀常驻的显式概念：重复遵循最短剩余工作会导致智能体间切换，引发前缀转移或重计算，从而降低有效服务能力。在相同操作点，下游门控策略也比SRPT取得了更低的平均JCT。因此，仅靠即时前缀局部性或任务进度都不足以最小化任务级JCT。

图1：在局部性优先LPM、进度优先SRPT和下游门控下，链式工作流在0.15任务/秒时的性能。
图2 (https://arxiv.org/html/2608.25523#S2.F2)揭示了这种冲突背后的机制。SRPT将一个任务推过工作流链，但每次转换到下一阶段都会改变常驻前缀并支付一次设置成本。相反，LPM将相同前缀的请求批处理以分摊设置成本，但这种局部性优先的顺序将服务阻塞在上游阶段，阻碍了下游进度。甘特图因此显示了优先考虑任务进度如何牺牲前缀局部性，而保持局部性如何延迟工作流完成。

（参考说明：图2：比较LPM和SRPT在A→B→C工作流中的甘特图。GPU内存一次只能容纳一个智能体前缀的KV缓存；每个请求耗时四个时间单位，每次前缀设置耗时一个时间单位。）
一个有效的调度器应将前缀常驻视为一个显式决策。它应合并共享前缀的请求以保持批处理效率，但当持续的复用延迟了任务完成时，应将服务转移到另一个前缀。目标是在每个调度决策内协调前缀复用和任务进度。

## III 问题形式化

所有任务遵循相同的已知有向无环图 \(G=(V,E)\)。任务 \(J_i\) 在时间 \(\tau_i\) 到达。每个节点 \(v \in V\) 是由一个智能体执行的阶段，在其所有前驱完成后变为就绪。一个阶段在产生输出之前可能发出一个或多个LLM请求。ReAct迭代和工具延迟事先未知；它们是运行时事件，决定了后续请求和阶段何时就绪。由智能体 \(a\) 产生的请求共享长度为 \(\ell_a\) 的静态前缀。令 \(C_{i,v}\) 表示任务 \(J_i\) 中阶段 \(v\) 的完成时间。任务完成时间和任务级JCT为：
\[
C(J_i) = \max_{v \in V} C_{i,v}, \qquad \text{JCT}(J_i) = C(J_i) - \tau_i. \tag{1}
\]
服务目标是在在线到达下最小化平均任务级JCT。

在调度点 \(t\)，令 \(S_t = (R_t, Q_t)\) 表示当前GPU状态，其中 \(R_t\) 是常驻智能体前缀集合，\(Q_t\) 是运行请求集合。调度动作选择一个决策后状态 \(S' = (R', Q')\)。集合 \(Q' \setminus Q_t\) 中的请求是新接纳的，而 \(Q_t \setminus Q'\) 中的请求被抢占。一个请求只有当其智能体前缀属于 \(R'\) 时才能属于 \(Q'\)。我们排除空闲的常驻前缀，因此 \(R' = \{ a(r) : r \in Q' \}\)。所选的联合状态必须满足：
\[
\sum_{a \in R'} \ell_a + \sum_{r \in Q'} d_r(t) \leq B_t, \tag{2}
\]
其中 \(d_r(t)\) 考虑了请求的动态后缀KV、保留的输出令牌和解码预留，\(B_t\) 是可用的令牌等效KV容量。同一智能体的多个请求只需支付一次静态前缀成本。

调度器观察就绪请求、当前GPU状态、任务到达时间、阶段进度以及工作流拓扑和智能体映射。未来的任务到达、未来的就绪时间、ReAct迭代以及未展开的工具输出是未知的。

## IV TOPAS：流程感知的前缀状态调度

### IV-A 设计概述

第II节 (https://arxiv.org/html/2608.25523#S2) 中的两个诊断揭示了请求级调度的局限性。当请求被逐个选择时，前缀常驻由请求顺序和服务运行时的缓存逐出策略间接决定。因此，不同的智能体前缀可能一起常驻，留给动态后缀和解码的KV容量太少。同时，即使另一个工作流阶段对任务完成更重要，服务也可能停留在可复用的前缀上。相反，TOPAS调度的是决策后的前缀-请求状态，直接选择常驻前缀及其下服务的请求。

对于每个候选前缀集，TOPAS在联合KV预算下构建一个兼容的请求分配。其基础效用（第IV-B节 (https://arxiv.org/html/2608.25523#S4.SSS2)）利用工作流DAG估计任务剩余LLM服务路径的缩短，在此进度与前缀移动和抢占之间进行权衡。一次前瞻（第IV-C节 (https://arxiv.org/html/2608.25523#S4.SSS3)）为可能服务于新释放的下游工作的前缀赋予价值，而任务老化（第IV-D节 (https://arxiv.org/html/2608.25523#S4.SSS4)）防止新到达的任务反复超越旧任务。第IV-E节 (https://arxiv.org/html/2608.25523#S4.SSS5) 通过枚举小型智能体池并对大型池使用有界贪婪搜索来搜索这些联合状态。最终得到的事件级分数使用预期剩余路径缩短作为任务完成进度的启发式估计。TOPAS在每个调度事件上贪婪地选择得分最高的生成下一状态，并随着系统状态变化重新评估该决策。

### IV-B