MFS: Multi-stage Flow Scheduling for LLM Serving
MFS: Multi-stage Flow Scheduling for LLM Serving #
Yijun Sun, Xudong Liao, Songrun Xie, Hao Chen, Han Tian, Wenxue Li, Yiming Zhang, Kai Chen iSING Lab, HKUST; SJTU; USTC | 2026-03 | https://arxiv.org/abs/2603.17456 Category: framework | Tags: serving, scheduling, network-contention, SLO-aware, disaggregation, MoE
§1 TL;DR #
MFS解决disaggregated MoE serving中三阶段通信（KV-cache复用 + collective comm + P2D传输）的网络争用问题，通过反转经典MLFQ的Reverse Multi-Level Queue实现Defer-and-Promote策略，无需精确laxity即可近似Least-Laxity-First调度，TTFT SLO达标率提升1.2×–2.4×。
§2 核心三问 #
Q1: 痛点 — 为什么现有disaggregated LLM serving的TTFT不达标？
现代LLM serving采用prefill-decode分离架构+EP/TP/SP多维并行。生成第一个token需要三阶段通信：(1) 从远程prefill unit获取可复用KV-cache blocks，(2) 模型并行的collective communication（如all-to-all），(3) Prefill-to-Decode (P2D)传输完整KV-cache。这三阶段的flow在共享网络链路上时间重叠并相互争用，导致：
- Intra-request contention：同一请求不同layer的KV传输(Stage 1&3)与collective comm(Stage 2)争抢带宽
- Inter-request contention：不同prefill unit的并发请求竞争链路，热门KV block的skewed popularity加剧
实测结果：争用使TTFT膨胀约50%，all-to-all CCT增加1.8×（Fig 5）。
现有调度方案的核心缺陷：stage-agnostic。Fair Sharing稀释Stage 2吞吐；SJF偏好小flow（KV传输）而饿死collective comm；EDF因Stage 3有explicit deadline而过度优先化；coflow调度管理数据并行flow但忽略跨stage依赖。所有方案都没有TTFT-to-flow-deadline的映射机制。
Paper Figure 4: 左侧为intra-request contention——同一请求的Layer-1/2/3的KV、EP、PD三阶段通信在时间上重叠并争用链路；右侧为inter-request contention——不同请求R1/R2/R3的通信在同一serving instance上竞争。红色虚线圈标注争用热点。
Q2: 方法 — Defer-and-Promote + Reverse Multi-Level Queue
MFS的核心观察：在prefill推进过程中，全局TTFT deadline逐步具体化(materialize)为flow级别的deadline。初始阶段(Stage 1&2)的flow-level deadline是implicit的（由TTFT和下游任务联合决定）；到最终阶段(Stage 3)，TTFT直接成为显式的flow-level bound。
基于此，MFS提出Defer-and-Promote调度原则：
- Principle #1 (Explicit-deadline flows)：P2D flow初始置于最低优先级，仅在Minimal Link Utilization (MLU)超过阈值时才提升——即只在剩余带宽恰好不足以按时完成时才提权
- Principle #2 (Implicit-deadline flows)：collective comm因直接阻塞当前layer计算而获最高隐式优先级；KV-cache prefetch基于Relative Layer Index (RLI)分配优先级，目标layer越近、优先级越高
实现机制为Reverse Multi-Level Queue (RMLQ)：反转经典MLFQ（经典是demote-down，RMLQ是promote-up）。$K$个优先级队列中，$P_1$（最高）保留给MLU≈1的P2D flow，$P_K$（最低）是所有P2D flow的默认入口，中间层由implicit-deadline flow按RLI占据。
核心技术壁垒：将全局TTFT deadline转化为per-flow优先级而无需精确laxity估计。这要求同时解决三个问题：(1) explicit-deadline flow的promote时机（MLU阈值设计），(2) implicit-deadline flow的相对紧迫度估计（RLI代理），(3) cross-stage争用的仲裁（队列分配 + tie-breaking规则）。反转MLFQ是使这一切在commodity switch硬件优先级队列上可实现的关键——通过layer粒度决策+DSCP包标记避免优先级抖动和包重排。
Q3: 结果
- 32-GPU真实testbed：TTFT降低20%–50%，non-overlapped CCT减少~50%（Fig 9）
- 大规模仿真（4个MoE模型 × 2种workload）：TTFT SLO达标率提升1.2×–2.4×（Fig 10-11）
- 在同等SLO hit rate下支撑1.2×–1.4×更高的请求速率
- Earliness分布显著改善：P2D flow不再过早完成浪费带宽（Fig 13）
§3 架构 / 方法图 #
系统总览 — RMLQ设计 #
Paper Figure 8: MFS的核心数据结构RMLQ。左侧communication library拦截通信任务，将implicit-deadline flow（Stage 1 KV cache reuse, Stage 2 collective comm）和explicit-deadline flow（Stage 3 P2D）分别映射到K级优先级队列。每个包被标记对应优先级的DSCP值，交换机硬件队列实现物理层面的流量隔离。
RMLQ是MFS的核心抽象。与经典MLFQ（新任务高优先级，随时间降级）相反，RMLQ将所有flow初始化在低优先级，仅在紧迫度增加时向上提升。这自然实现了Defer-and-Promote：带宽默认分给立即需要的collective comm，P2D flow只在deadline临近时才争抢带宽。
网络争用场景 #
Paper Figure 3: 展示disaggregated集群中三阶段通信的争用场景。Prefill unit内部EP=32的all-to-all通信(Stage 2, 蓝色)、跨unit的KV cache reuse(Stage 1, 紫色)、到Decode unit的P2D transfer(Stage 3, 橙色)共享leaf-spine网络的bottleneck链路。红色虚线标注争用位置。
请求生命周期 #
调度决策细节 #
Explicit-deadline (P2D) 调度：MLU驱动的lazy promotion。
$$\mathrm{MLU}_i(t) = \frac{\mathrm{Size_{rem}}(t)}{\mathrm{Time_{rem}}(t) \cdot B \cdot (1 - \rho)}$$
Flow在$P_j$被promote到$P_{j-1}$当$\mathrm{MLU}_i(t) \geq \tau_j$。阈值$\{\tau_j\}$将$[0,1]$ MLU空间划分为$K$个优先级带。决策在layer边界而非per-packet执行，避免优先级抖动。
Implicit-deadline 调度：RLI代理紧迫度。
- $\mathrm{RLI} = 0$：当前layer需要的数据 → 最高隐式优先级（deferral立即stall GPU）
- $\mathrm{RLI} > 0$：未来layer → 可延迟，优先级随RLI递减
Stage 2 (collective comm) 定义上RLI=0，始终获得implicit-deadline flow中的最高优先级。
Cross-stage仲裁：同一优先级层级内，implicit-deadline flow（Stage 2）tie-break胜过explicit-deadline flow（P2D），因为前者的deferral会立即stall计算。
§4 作者证明 #
符号表 #
| Symbol | Definition |
|---|---|
| $L$ | Transformer layers |
| $\ell$ | Current layer index |
| $K$ | Number of priority queues in RMLQ |
| $P_i$ | Priority queue $i$ ($P_1$ highest, $P_K$ lowest) |
| $\tau_j$ | MLU threshold for promotion from $P_j$ to $P_{j-1}$; $\tau_K = +\infty$ |
| $\mathrm{Size_{rem}}(t)$ | Remaining data to transmit at time $t$ |
| $\mathrm{Time_{rem}}(t)$ | Time remaining before TTFT deadline at $t$ |
| $B$ | Link bandwidth |
| $\rho$ | Background traffic utilization ratio |
| $D_r$ | TTFT deadline for request $r$ |
| $\mathrm{RLI}$ | Relative Layer Index: distance from current execution layer to target layer |
| $\mathrm{MLU}_i(t)$ | Minimal Link Utilization for flow $i$ at time $t$ |
核心方程物理意义 #
MLU (Eq. 1):
$$\mathrm{MLU}_i(t) = \frac{\mathrm{Size_{rem}}(t)}{\mathrm{Time_{rem}}(t) \cdot B \cdot (1 - \rho)}$$
分子是剩余待传数据量；分母是deadline前可用的有效带宽容量（总带宽$B$扣除background traffic占比$\rho$再乘以剩余时间）。MLU表示"为使flow按时完成，至少需要占据多大比例的链路带宽"。
- $\mathrm{MLU} \ll 1$：flow有充裕slack，可安全defer
- $\mathrm{MLU} \to 1$：flow必须立即获得几乎全部可用带宽才能按时完成 → 紧急promote
- $\mathrm{MLU} > 1$：即使独占带宽也无法按时完成 → 触发feasibility pruning
为什么用$1-\rho$而非$1$：$\rho$是对当前链路background利用率的保守估计。不扣除$\rho$会低估紧迫度，导致promote过晚。
6项检查 #
| # | Check | Result |
|---|---|---|
| 1 | 边界: flow完成 ($\mathrm{Size_{rem}}=0$) | $\mathrm{MLU}=0$，无需优先级 ✓ |
| 2 | 边界: deadline迫近 ($\mathrm{Time_{rem}} \to 0$) | $\mathrm{MLU} \to \infty$，触发立即promote到$P_1$ ✓ |
| 3 | 单调性 | 时间流逝中$\mathrm{Time_{rem}}$单调递减；若flow被defer则$\mathrm{Size_{rem}}$不变 → MLU单调递增 → flow只promote不demote ✓ |
| 4 | 量纲 | $[\text{bytes}] / ([\text{s}] \times [\text{bytes/s}] \times [\text{无量纲}]) = [\text{无量纲比例}]$ ✓ |
| 5 | 阈值语义 | $\tau_j$将$[0,1]$切分为$K$段；$\tau_K=+\infty$使所有新flow从$P_K$开始；$\tau_2$接近1使只有真正紧急的flow到达$P_1$ ✓ |
| 6 | 实例验证 (Table 1) | Flow C: size=3, remain_time=0 → $\mathrm{MLU}=\infty$ → 立即$P_1$; Flow A: size=2, remain=9, deadline=18 → $\mathrm{MLU}$很小 → 留在$P_K$; Flow B: size=4, remain=6, deadline=12 → 中等MLU → 中间优先级。与Fig 8(d) Defer-and-Promote行为一致 ✓ |
RLI的隐式deadline建模 #
RLI没有显式方程，而是一个整数距离度量：当前执行layer $\ell$与目标KV-cache所需layer $\ell'$之间的距离$\ell' - \ell$。物理意义是"还有多少layer的计算时间作为缓冲"——layer执行时间大致均匀，所以RLI近似线性映射到可用slack。
RLI=0时deferral立即stall GPU（zero slack），所以Stage 2 collective comm定义上获得最高隐式优先级。RLI>0的KV prefetch有层数作为buffer，可以承受一定deferral。
§5 实验与数据 #
争用影响量化（Motivation measurement） #
Paper Figure 5: 16-GPU testbed (50 Gbps/GPU), Mixtral 8×7B, TP=1 EP=8, QwenB-agent workload, 1 req/s/GPU, 65% prompt reuse. (a) 争用使TTFT分布右移约50%（归一化TTFT中位数从~0.8上升到~1.2）; (b) all-to-all CCT的CDF显示争用下CCT近乎翻倍(1.8×)，从~30ms中位膨胀到~55ms。
这张图是MFS立论的基石：它证明网络争用——而非计算或内存——是disaggregated MoE serving中TTFT违规的主因。~50%的TTFT膨胀意味着即使计算完全无bottleneck，网络调度不当就足以导致大量SLO violation。
Testbed实测（32-GPU, Mixtral-8×7B） #
Paper Figure 9: 8-server 32-GPU testbed, Mixtral-8×7B. (a) MFS将normalized TTFT降低约20%（QwenA-Conv）到50%（QwenB-agent）; (b) normalized CCT减少约30%–55%。QwenB-agent（高复用率、短序列、密集inter-request争用）获益更大。
QwenB-agent workload获益更大的原因：65%的prompt复用率导致大量KV-cache fetch请求集中在少数"hot" remote unit上，inter-request争用更严重。MFS的feasibility check + defer策略在此场景下精确抑制了bandwidth浪费。
大规模仿真 — Conversation workload (QwenA) #
Paper Figure 10: 4个MoE模型(Mixtral-8×22B, DBRX, Qwen3-Coder, Grok2)在conversation workload下的SLO attainment vs per-GPU request rate。MFS（绿色）在所有模型和负载点上一致性超越FS/SJF/EDF/Karuna。
关键观察：(1) 在低负载下所有方案接近100% SLO attainment，差异在中高负载才拉开；(2) MFS的优势在DBRX上最明显（~2×），因DBRX的EP度高导致all-to-all通信量大，争用更严重；(3) Karuna（coflow scheduler）表现不优于EDF，因为它只管data-parallel coflow而忽略cross-stage依赖。
大规模仿真 — Agent workload (QwenB) #
Paper Figure 11: Agent workload下的SLO attainment。与conversation workload相比，MFS的优势更显著——在高负载区域baseline几乎全部降至<25%而MFS仍维持50%+。Agent workload的短序列+高复用率+突发性加剧了inter-request争用。
Agent workload更能区分MFS的价值：(1) 短序列意味着更多请求在单位时间内竞争网络；(2) 高KV复用率使hot-block争用集中化；(3) 严格TTFT SLO（agentic pipeline的timeout要求）对scheduling质量更敏感。
CCT与Earliness breakdown #
Paper Figure 13: DBRX, QwenA conversation, 0.7 req/s/GPU. (a) Normalized CCT CDF: MFS将CCT中位数从~0.4降至~0.15，约60%改善。(b) Normalized earliness CDF: MFS的earliness集中在0附近（just-in-time完成），而其他方案的P2D flow过早完成（earliness<0），浪费了本可让给collective comm的带宽。
Fig 13(b)是Defer-and-Promote机制的直接验证：earliness分布紧贴0说明P2D flow恰好在deadline前完成，而非提前占用带宽。FS/SJF/EDF的负earliness（过早完成）正是它们浪费带宽、挤压collective comm的证据。
关键数值汇总 #
| Metric | MFS vs Baselines | Evidence |
|---|---|---|
| TTFT SLO attainment | 1.2×–2.4× improvement | Fig 10-11, across 4 models × 2 workloads |
| Non-overlapped CCT | ~50% reduction | Fig 9(b), Fig 13(a) |
| Sustainable request rate at same SLO hit | 1.2×–1.4× higher | Fig 10-11 saturation points |
| TTFT reduction (testbed) | 20%–50% | Fig 9(a) |
| Earliness | Near-zero (just-in-time) | Fig 13(b) |
§6 论证链 #
| Step | Claim | Evidence | §Ref |
|---|---|---|---|
| 1 | Disaggregated MoE serving的TTFT违规主要来源于三阶段通信的网络争用 | 实测TTFT膨胀~50%, CCT增加1.8× (Fig 5) | §2.2 |
| 2 | 现有flow/coflow调度器因stage-agnostic而无法有效解决此争用 | FS稀释Stage 2, SJF偏好小flow, EDF过度优先化Stage 3, coflow忽略cross-stage依赖 (Fig 6-8, Table 1) | §2.3, §3.2 |
| 3 | TTFT deadline在prefill推进过程中逐步从implicit具体化为explicit | Stage 1&2的deadline由TTFT和下游任务联合决定(implicit); Stage 3的deadline等于TTFT本身(explicit) — 结构性质允许分级调度 | §3.2 |
| 4 | Defer-and-Promote通过RMLQ近似Least-Laxity-First调度而无需精确laxity | MLU量化explicit-deadline flow的紧迫度; RLI代理implicit-deadline flow的相对紧迫度; layer粒度promotion保证switch硬件兼容 | §4.2-4.5 |
| 5 | MFS在4个MoE模型上一致性提升SLO attainment 1.2×–2.4× | Simulation: Mixtral-8×22B, DBRX, Qwen3-Coder, Grok2 (Fig 10-11); Testbed: Mixtral-8×7B (Fig 9) | §6.1-6.2 |
| 6 | CCT减半 + earliness归零证明mechanism生效 | CCT CDF左移(Fig 13a); earliness集中在0(Fig 13b) — 与Defer-and-Promote的设计意图精确匹配 | §6.2 |
§7 实现 cross-reference #
[实现未公开]
MFS描述为pluggable module集成到NCCL + Mooncake + vLLM中，但截至2026-05未公开源代码。
实现架构要点 #
- NCCL adapter: 拦截collective communication任务，在host-side软件队列中执行RLI-based优先级排序后再提交
- Mooncake adapter: 拦截KV-cache transfer任务（Stage 1 & 3），执行MLU计算和priority assignment
- DSCP tagging: 将RMLQ优先级映射到IP header的DSCP字段，commodity switch的hardware priority queue实现物理隔离
- Centralized coordinator: 维护所有active requests的deadline和进度，执行inter-request scheduling（feasibility check + EDF ordering）
- Layer-progress callback: vLLM推理引擎在每层完成后通知MFS，触发RLI更新和MLU重计算
核心技术壁垒（补充） #
RMLQ的工程难点在于让layer-granularity promotion在commodity switch上可行。如果per-packet重新标记priority，会导致同一flow的包在switch不同queue中被乱序消费。Layer-granularity确保一个layer内的所有包标记一致，batch promotion在layer边界原子性地完成。这需要communication library和推理引擎之间精确的layer-progress同步。
关键实现细节 #
- DSCP到switch queue的映射：需要switch配置将DSCP值映射到对应的hardware priority queue。现有datacenter switch（如Mellanox SN系列）标准支持8个优先级队列，足以支撑MFS的$K$级RMLQ（论文默认$K \leq 8$）。
- Background traffic $\rho$ 的估计：MLU公式中$\rho$不是实时测量的瞬时值，而是一个配置参数（保守估计）。这意味着MLU的紧迫度评估天然偏保守——宁可早promote也不冒deadline miss的风险。实际部署中$\rho$需要根据集群flow profile调优。
- KV prefetch (Stage 1): 提前几层开始传输，RLI决定何时提升优先级
- P2D transfer (Stage 3): defer到deadline临近才传输，通过MLU控制promote节奏
- 无swap to CPU/disk机制（不在MFS scope内）
- Fair Sharing (FS): 标准TCP行为，所有flow平分带宽
- Shortest Job First (SJF): 按flow大小排序
- Earliest Deadline First (EDF): 按deadline排序（Stage 3有explicit deadline，其他implicit）
- Karuna: Deadline-aware coflow scheduler（管理data-parallel coflow但不管cross-stage）
- SLO attainment: 满足TTFT deadline的请求占比（主指标）
- Normalized CCT: 相对于无争用baseline的collective completion time
- Normalized earliness: $(D_r - t_{\text{complete}}) / D_r$，0表示just-in-time，负值表示过早完成
- Testbed: 8 servers × 4 NVIDIA 3090 GPUs × 2 Mellanox NICs = 32 GPU, single ToR switch, 50 Gbps/GPU effective
- Simulation: 模拟更大规模集群（具体GPU数量未详细说明），4个MoE模型
- User-facing API: 无独立API。MFS作为pluggable module嵌入vLLM+NCCL+Mooncake stack，对serving engine的上层API透明
- Config surface: 主要参数为$K$（优先级队列数）、$\{\tau_j\}$（MLU阈值）、$\rho$（background traffic估计）。论文提供了sensitivity analysis但未给出明确的auto-tuning方案
- Migration cost: 需要(1) NCCL和Mooncake的adapter集成（代码层面的hook），(2) switch的DSCP-to-queue mapping配置，(3) vLLM的layer-progress callback集成。中等复杂度——非零侵入但不需要fork entire engine
- 截至2026-05，未合入任何主流开源框架（vLLM/SGLang/TRT-LLM）
- 未公开源代码
- 论文来自HKUST iSING Lab（Kai Chen组），networking方向背景
- MFS的DSCP-based方案依赖switch支持hardware priority queues——这在datacenter交换机中是标准功能，但需要运维配置
- 对下游的强制要求：communication library必须暴露task拦截点，推理引擎必须提供layer-progress callback
§8 System Scope #
| Dimension | Value |
|---|---|
| Stage coverage | Prefill（三阶段通信全在prefill阶段）；P2D transfer跨越到decode |
| Serving / training | Serving（online, latency-sensitive） |
| Batching | Continuous batching implied（多request并发prefill） |
| Parallelism owned | 网络调度层：不改变TP/PP/EP/SP的计算逻辑，仅调度它们产生的通信flow |
| Parallelism delegated | 计算调度（request batching, chunked prefill）→ vLLM; collective algorithm → NCCL; KV transfer → Mooncake |
| Deployment | Multi-node, disaggregated prefill-decode |
MFS的独特定位：它不是一个完整的serving engine，而是嵌入existing engine（vLLM）和communication library（NCCL/Mooncake）之间的网络调度中间层。这种pluggable设计意味着MFS可以与不同serving engine组合，但也意味着它对compute scheduling没有控制力。
§9 Scheduling & Resource Management #
Scheduling decisions #
| Aspect | MFS Design |
|---|---|
| Granularity | Flow-level，决策在layer边界执行 |
| Preemption | 隐式——低优先级flow被高优先级flow starve（bandwidth preemption），不会kill/restart |
| Admission control | Feasibility check: 如果request无论如何都无法满足TTFT deadline，其flow被deprioritize以避免阻塞可行请求 |
| Fairness | Per-request TTFT deadline驱动优先级（EDF-like at request level），无per-tenant保证 |
| Inter-request ordering | 基于TTFT deadline的EDF + feasibility pruning |
| Intra-request ordering | Stage 2 > Stage 1 (by RLI) > Stage 3 (deferred, MLU-promoted) |
Memory management #
MFS不直接管理KV-cache内存，而是调度KV-cache的传输。KV-cache allocation/eviction由Mooncake处理。MFS控制的是传输的timing和priority：
§10 Workload Characterization #
| Workload regime | MFS | Baseline (FS/SJF/EDF/Karuna) | Why |
|---|---|---|---|
| MoE + EP + 高争用 | 强优势 (1.5–2.4× SLO) | CCT被KV transfer挤压 | Multi-stage awareness精确隔离Stage 2 |
| Agent workload (短序列, 高KV复用, 突发) | 最强优势 (接近2.4×) | Inter-request contention严重, 所有baseline崩溃 | Feasibility pruning + defer避免hot-block堆积 |
| Conversation workload (较长序列, 中等复用) | 中等优势 (1.2–1.5×) | 争用存在但less severe | Collective comm保护仍有效 |
| 低负载, 少量并发请求 | 微弱优势 | 争用有限, 所有方案都能达标 | 几乎无争用需要resolve |
| Dense model (无EP, TP-only) | 论文未评估 | 缺少Stage 1的KV复用争用 | 争用降至2阶段, MFS价值可能降低 |
| 极高$\rho$ (background traffic heavy) | 未评估, 但MLU的$\rho$项提供适应性 | 更容易争用 | MLU保守估计在高$\rho$下自然更快promote |
论文主要展示了MFS "赢"的regime。缺失的regime：(1) dense model（无EP的all-to-all争用小得多），(2) 单节点（intra-node NVLink不经过switch，DSCP无用），(3) 超大规模集群（centralized coordinator可能成为bottleneck）。
§11 Evaluation Details #
Baselines与公平性 #
论文未提及baseline的调优细节（如Karuna的参数选择）。FS/SJF/EDF是标准策略无需调参。
Metric定义 #
"Throughput"在本文中体现为"在同等SLO attainment下的最大可持续request rate"，不是传统的output tok/s。
Hardware setup #
§12 API & Usability #
§13 Adoption & Ecosystem #
§14 Deployment Context #
| Dimension | Value |
|---|---|
| Serving stage | Prefill only / P2D bridge to decode |
| Concurrency regime | Mid-to-high（≥8并发prefill requests，才有足够争用让MFS发挥作用） |
| Hardware affinity | 需要多NIC + switch的hardware priority queue; 3090/H100/H800均可; NVLink intra-node通信不受益 |
| Ecosystem integration | vLLM (scheduler) + NCCL (collective) + Mooncake (KV transfer) + commodity Ethernet switch |
| Integration cost | Adapter hook到NCCL/Mooncake + switch DSCP配置 + vLLM layer callback; 不需要fork engine |
| Migration path | vLLM用户需要: (1) 部署MFS coordinator service, (2) 替换NCCL/Mooncake library为MFS-instrumented版本, (3) 配置switch priority queues, (4) 设置TTFT SLO参数 |
MFS解决的问题（multi-stage网络争用）在以下场景最相关：大规模disaggregated MoE serving（EP度高、KV复用率高、请求密集）。对于小规模部署（单机或2-4节点）、dense model、或NVLink-heavy拓扑，MFS的价值有限。