FastServe: Fast Distributed Inference Serving for Large Language Models #

§1 TL;DR #

利用 LLM 推理的 semi information-agnostic 特性（input length 已知、output length 未知），设计 skip-join MLFQ 调度器消除 head-of-line blocking，配合 proactive KV cache swapping 管理内存开销，吞吐比 vLLM 提升高达 31.4×。

§2 痛点 / 方法 / 结果 #

Q1 痛点 #

现有 LLM 推理系统（Orca、vLLM）使用 FCFS + run-to-completion 调度，导致严重的 head-of-line (HoL) blocking：

• 实测数据（Fig. 1）：ShareGPT 工作负载在 load=0.9 时，queuing delay 占总延迟的 98%。即使 Alpaca 在 load=1 时也有 92.7%。原因：真实工作负载的输入/输出长度高度倾斜（长尾分布），长请求阻塞后续短请求。
• 高达 90% 的延迟来自排队而非执行——传统的执行效率优化（更快的 kernel、更好的 batching）无法触及此瓶颈。

Why not SRPT? LLM 推理的总执行时间 = prefill time（与 input length 成正比，已知）+ decode time（与 output length 成正比，未知）。无法直接应用 SRPT。

Why not naive MLFQ? 标准 MLFQ 将新任务放入最高优先级队列，但 LLM 首次迭代（prefill）时间可能远超最高队列的 quantum——要么中途抢占（浪费已完成计算），要么不抢占（HoL blocking 回归）。

Q2 方法 #

Skip-Join MLFQ 调度器（§4.1）：

$n$ 级优先级队列 $Q_1, \ldots, Q_n$，quantum $q_1 < q_2 < \ldots < q_n$（相邻比 = 2）。三个关键操作：

1. Skip-Join ❶：新任务通过 profiler 预测 prefill time $t_{\text{init}}$，直接加入满足 $q_i \geq t_{\text{init}}$ 的最高优先级队列（跳过更高的队列）。
2. Demotion ❷：耗尽 quantum 后降级 $\eta$ 级。
3. Starvation Prevention ❸：等待超过 $\alpha$（默认 300ms）的任务提升回 $Q_1$。

Semi information-agnostic 关键洞察：虽然 output length 未知，但每次迭代的执行时间是可预测的（由 hardware + model + input length 确定），可通过轻量 profiling 预先收集。

Proactive KV Cache Management（§4.2）：

Skip-join MLFQ 的抢占特性使 KV cache 内存开销暴增（最高 7× vs FCFS，Fig. 8）。解决方案：

• 将 KV cache 存储空间从 GPU 扩展到 host memory
• Proactive swapping：在当前 batch 执行期间，预判下批次需要的 KV tensor 并异步 PCIe 传输（与 GPU 计算重叠），避免 GPU idle
• Swap 优先级：基于 Estimated Next Scheduled Time (ENST)——ENST 最大的先 swap out，ENST 最小的先 swap in

ENST 计算：

$$\text{ENST}(i) = \min(T_{\text{promote}}(i),\ T_{\text{execute}}(i))$$

其中 $T_{\text{promote}}$ = starvation prevention 触发前的等待时间，$T_{\text{execute}}$ = 所有更高优先级任务的 quantum 之和。

Distributed Execution（§4.3）：

• Tensor parallelism + pipeline parallelism 支持 175B 规模模型
• Pipeline 级别的调度：每个 stage 完成后选择最高优先级 pending job
• KV cache 分布式管理：每 GPU 管理本地 KV 分片，swap 指令随 pipeline 传播

核心技术壁垒：semi information-agnostic 的形式化——将 LLM 推理视为"input length 已知但 output length 未知"的调度问题，恰好介于 information-agnostic（经典 MLFQ）和 information-aware（SRPT）之间。Skip-join 机制是对这一中间状态的最优利用：用已知的 prefill time 跳过不必要的高优先级队列，同时保留 MLFQ 对未知 output length 的鲁棒性。

Q3 结果 #

• vs vLLM（v3/NSDI）：同等延迟约束下吞吐提升 31.4×（平均延迟）/ 17.9×（尾延迟）。
• vs Orca（v1）：平均 JCT 改善 5.1×，尾 JCT 改善 6.4×。
• 调度器消融：skip-join MLFQ 比 naive MLFQ 快 3.6×–41×（§6.3）。
• 内存管理消融：proactive swapping 比 defer 策略快 2.3×–3.5×（§6.3）。
• 可扩展性：6–16 GPU 上线性受益，FastServe vs Orca 保持 3.5×–4× 优势。

§3 架构 / 方法图 #

flowchart TB subgraph Input ["Request Arrival"] JP["Job Pool"] Prof["Job Profiler
(predict t_init)"] end subgraph Scheduler ["Skip-Join MLFQ Scheduler"] Q1["Q₁ (highest priority, quantum q₁)"] Q2["Q₂ (quantum q₂ = 2q₁)"] Q3["Q₃ (quantum q₃ = 4q₁)"] Qn["Q_n (lowest priority)"] Q1 --- Q2 --- Q3 --- Qn end subgraph Memory ["KV Cache Management"] GPU_KV["GPU KV Cache"] Host_KV["Host Memory KV Cache"] ENST["ENST Ordering"] end subgraph Exec ["Distributed Execution Engine"] S0["Pipeline Stage 0"] S1["Pipeline Stage 1"] S2["Pipeline Stage ..."] end JP --> Prof Prof -->|"skip-join to Q_i
where q_i ≥ t_init"| Scheduler Scheduler -->|"select top priority
up to MaxBatchSize"| Exec Exec <--> GPU_KV GPU_KV <-->|"proactive swap
(overlap with compute)"| Host_KV ENST --> GPU_KV

Request lifecycle：Request → Job Profiler（预测 prefill time）→ skip-join 到适当队列 → scheduler 从最高优先级队列选取 batch → 分发到 pipeline stages 执行一次迭代 → 生成 token / 完成 / 降级 / 被 preempt。

Scheduling 决策点：

决策	粒度	抢占策略	公平性保证
Batch 组建	迭代级（每生成一个 token）	KV cache swap out（proactive）	Starvation prevention（$\alpha$ 阈值）
Queue 分配	请求到达时	—	Skip-join 避免高优先级拥堵
Pipeline 调度	Stage 级	选择最高优先级 pending job	MLFQ 优先级继承

Memory management：

操作	触发条件	策略
Swap out	任务被 preempt 且 ENST 大	ENST 最大优先 swap out
Swap in	任务即将被调度	ENST 最小优先 swap in
Defer	仅在 GPU 和 host 均满时	阻塞新到达任务

KV cache 大小公式：

$$\text{KV cache bytes} = 4 \times l \times h \times (s + t)$$

$l$ = layers, $h$ = hidden dim, $s$ = input length, $t$ = output length。OPT-175B 单请求（$s=512, t=1$）= 2.3 GB。

§4 作者证明 #

符号表 #

符号	含义
$Q_i$	第 $i$ 优先级队列
$q_i$	第 $i$ 队列的 quantum
$t_{\text{init}}$	首次迭代（prefill）执行时间
$\alpha$	Starvation prevention 阈值（默认 300 ms）
$\eta$	降级步数
$l, h, s, t$	Layers, hidden dim, input length, output length
ENST	Estimated Next Scheduled Time

方程物理意义 #

KV cache size：$4lh(s+t)$——factor 4 来自 2 bytes/value × 2 (key + value)。每新增一个 output token，KV cache 增长 $4lh$ bytes（OPT-175B: 4.6 MB/token）。

ENST：权衡两条路径——(1) starvation prevention 定时器到期被提升回 $Q_1$；(2) 所有更高优先级任务自然耗尽 quantum 后被调度到。取较小值作为预估。

无形式化吞吐 / 延迟模型——论文不提供解析性能模型，所有对比通过实验。

6 项检查 #

1. Skip-join 正确性：当 $q_i \geq t_{\text{init}}$ 时，首次迭代不超时——避免了 prefill 被中途抢占的浪费。✔
2. MLFQ 降级语义：耗尽 quantum 后降级 $\eta$ 级——保留 MLFQ 对未知 job size 的逼近 SRPT 特性。✔
3. Starvation prevention：等待超过 $\alpha$ 提升回 $Q_1$——防止低优先级任务永远不被调度。✔
4. Proactive swap 无阻塞：PCIe 传输与 GPU 计算重叠——GPU 不因 swap 而 idle（vs reactive swap 需等待）。✔
5. 杀死-重算的死锁：killed job 被 starvation prevention 提升 → 可能杀死提升它的 job → 循环。Proactive swap 避免此问题。✔
6. KV cache 上界：swap out 的 block 数不超过 GPU 物理 block 总数——host memory 容量充足时不会 OOM。✔

§5 实验与数据 #

实验配置 #

模型	参数量	Layers	Heads	Hidden
GPT-3 2.7B	5.4 GB	32	32	2560
GPT-3 66B	132 GB	64	72	9216
GPT-3 175B	350 GB	96	96	12288

硬件：2× AWS p4d.24xlarge（8× A100-40GB / node，NVLink，PCIe 4.0×16，1152 GB host memory）。

端到端性能（GPT-175B, 16 A100s, v1） #

对比维度	FastServe vs Orca	FastServe vs FasterTransformer
Avg JCT vs load	1×–4.3× 改善	1.9×–11.4×
Avg JCT vs burstiness	2.3×–5.1×	7.4×–12.2×
Avg JCT vs skewness	1.9×–3.9×	3.6×–10.6×

v3/NSDI 对比 vLLM：31.4× / 17.9× throughput improvement under same avg / tail latency constraints.

调度器消融（GPT-3 2.7B, 1 A100） #

对比	Skip-Join MLFQ 优势
vs MLFQ-preemption	高达 24×（高 load 下抢占浪费计算）
vs MLFQ-no-preemption	高达 32×（大任务在 Q1 阻塞）
Quantum ratio 敏感度	skip-join 对 quantum ratio 几乎不敏感

内存管理消融 #

对比	FastServe 优势
vs Defer	高达 3.5×
vs Reactive-offload	高达 1.6×
vs 小 cache slots	高达 1.8×

可扩展性（GPT-3 66B, 6–16 GPUs） #

GPUs	FastServe vs Orca (Avg JCT)	FastServe vs Orca (P90 JCT)
6	3.5×	2.2×
16	4.0×	6.4×

Workload characterization #

负载场景	FastServe	FCFS (vLLM/Orca)	原因
高 load + 高 skew	大幅领先	HoL blocking 严重	长任务阻塞，skip-join 避开
低 load	差距小	排队少	MLFQ 退化为 FCFS
均匀 job size	优势较小	无 HoL blocking	skip-join 无用武之地
高 burstiness	大幅领先	突发拥塞	proactive swap 吸收峰值

论文承认的弱项 #

1. 低负载时 FastServe ≈ FCFS（MLFQ 退化）。
2. 均匀 job size 分布下优势消失（无 HoL blocking）。
3. v1→v3 数字差异巨大（5.1× → 31.4×），主要因基线和指标定义变化，非系统本身提升。

§6 论证链 #

步骤	论点	证据
1	LLM serving 中高达 90% 延迟来自排队而非执行	§1 Fig. 1（ShareGPT load=0.9: 98% queuing）
2	FCFS + run-to-completion 导致 HoL blocking；output length 未知使 SRPT 不可用	§2.3（challenge 1）；§4.1 strawman 分析
3	LLM 推理是 semi information-agnostic：input length 已知 → 每次迭代时间可预测	§4.1 Fig. 5（profiling 数据）
4	Skip-join MLFQ 利用已知 prefill time 避免不必要的高优先级拥堵	§4.1 Algorithm 1；Fig. 7（skip-join avg latency 3.3 vs FCFS 4.23 vs MLFQ 5）
5	抢占式调度产生 7× KV cache 内存开销，proactive swap 通过 GPU-PCIe overlap 解决	§4.2 Fig. 8/9（proactive vs reactive swap）
6	端到端验证：31.4× throughput improvement over vLLM	§6 全部实验

§7 实现 cross-reference #

代码：~10,000 行 Python + C++

• 执行引擎：基于 FasterTransformer（v1）/ vLLM + PagedAttention（v3）
• Pipeline 扩展：修改 FasterTransformer 支持 inter-batch pipelining（多 batch 填充 pipeline bubbles）
• KV cache manager：MPI 分布式实现，CUDA stream 异步 swap
• Scheduler：Python 实现，skip-join 逻辑 + ENST 计算

关键实现细节 #

1. Profiler 轻量性：每种 (hardware, model, input_length) 组合的迭代时间可离线 profiling 一次——prefill time 与 input length 近似线性（Fig. 5），decoding time 近似常数。无需在线推断 output length。
2. Proactive swap pipelining：当前 batch 的 GPU 执行与下一 batch 的 PCIe swap 通过多 CUDA stream 重叠。OPT-175B 16 GPU：decode ~60 ms / token，swap 2.3 GB ~36 ms via PCIe 4.0×16——swap 可完全隐藏。

部署上下文 #

• Serving stage：prefill + decode 均覆盖
• Concurrency regime：中高并发（交互式应用场景）
• Hardware affinity：大模型（≥ 66B）+ 多 GPU 最大受益（pipeline parallelism 使 inter-batch pipelining 有意义）
• Ecosystem：v3 集成 vLLM + PagedAttention
• Migration path：替换 vLLM/Orca 的调度层；执行引擎保持不变