PREBLE_EFFICIENT DISTRIBUTED PROMPT SCHEDULING FOR LLM SERVING

Preble 研究的是一个请求路由问题:当一个请求进来时,应该把它发给已经缓存了相同 prompt 前缀的 GPU,还是发给负载更轻的 GPU?前者能少做 prefill,后者能少排队。Preble 的贡献是把 KV cache 的位置和 GPU 负载放进同一个调度决策。

1. 为什么多 GPU 会出现这个问题?|第 1–4 页

假设 100 个用户都在问同一份长文档,每条请求的结构是 [同一份文档][不同的问题]。第一条请求做完 prefill 后,GPU 可以保留文档部分的 KV。后续请求只要从开头匹配到相同的 token 前缀,就可以复用这部分 KV,只为新的问题部分做 prefill,再生成答案。

单个模型实例里,这主要是缓存管理问题。多个实例里,还多了一层路由选择:

路由方式会发生什么
Round-robin,轮流发给各 GPU每张 GPU 都可能各算一遍文档,并各存一份 KV
始终发给缓存匹配最长的 GPU文档突然变热门时,请求会在同一张 GPU 上排队
Preble通常让高复用请求走已有缓存,同时给低负载 GPU 分配工作,必要时复制热点前缀

论文研究的五类 workload 包括工具调用、具身 agent、代码生成、视频问答和长文档问答。按论文的统计,85%–97% 的 prompt token 属于至少与另一条请求共享的前缀。这个数字衡量的是数据里的复用潜力,实际命中还取决于请求被发到哪张卡,以及缓存是否已经被驱逐。

2. 核心算法 E² 怎么选 GPU?|第 4–6 页,算法 1–2 见第 20–21 页

全局 scheduler 用 radix tree 记录 token 前缀,以及哪些 GPU 缓存了这些前缀的 KV。对一条新请求,它先找最长的已缓存前缀,再决定 Exploitation 或 Exploration。

  • Exploitation,优先复用。 如果一个 10,000-token 的 prompt 已经能命中 8,000 个 token,就在持有最长匹配前缀的 GPU 中选。若有多个候选,再比较它们的负载代价。
  • Exploration,考虑所有 GPU。 如果同样长的 prompt 只命中 2,000 个 token,还是要为剩下 8,000 个 token 做 prefill。这时,调度器可以把请求发到其他 GPU,减少负载集中,并让新算出的前缀留在那里供后续请求复用。

算法用的是一个简单的启发式:命中 token 数超过 prompt 的一半,就走 Exploitation。 在 Exploration 中,通常会比较下面三项,统一用估算的 GPU 计算时间表示:

[ \mathrm{Cost}i = \underbrace{L_i}{\text{近期 prefill 和 decode 负载}} + \underbrace{M_i}{\text{驱逐缓存带来的预计重算代价}} + \underbrace{P_i}{\text{新请求未命中部分的 prefill 代价}} ]

这里最值得看的是 (M_i)。一张 GPU 即使看起来很空,新请求也可能挤掉一段经常被访问的 KV,让后续请求重新做 prefill。Preble 用被驱逐前缀的重算时间乘以近期命中频率估算这个代价。另有一个优先规则:如果某张 GPU 的工作明显偏向 decode,Exploration 可以先把偏 prefill 的请求派给它,利用 decode 时相对空闲的算力。

3. 热点突然变化怎么办?|第 6–7 页

这里有个关键细节:单次 E² 决策仍然可能把大量高命中请求送到同一张卡。所以 Preble 还在后台做负载调整。如果某张 GPU 持续过载,系统会把一部分后续请求改派到较轻的 GPU。如果一个热门前缀的请求量仍然太高,系统就把这个前缀复制到多个 GPU,让它们一起分担。多存一份 KV 要占显存,但可以把原本集中在一张卡上的排队分散开。

全局 scheduler 决定请求去哪一个模型实例,local scheduler 决定这个实例下一轮跑哪些请求。本地调度会给缓存命中比例高的请求更多 batch 名额,同时也从低命中组取请求,减少长时间等待。对很长的未缓存 prompt,它还会用 chunked prefill 分段处理。

4. 实验说明了什么?|第 8–10 页,图 3–5

论文用 Mistral 7B 和 Llama-3 70B 做评估。主实验里的 SGLang baseline 已经支持单实例 prefix caching,但跨实例采用 round-robin。相对这个 baseline,Preble 在所测配置里的平均端到端延迟改善了 1.5–14.5×,p99 延迟改善了 2–10×。高负载下差距更明显。代码生成的平均延迟收益较小,因为它输出更长,端到端时间里有更大一部分花在逐 token decode 上。

可以把它和 PagedAttention 放在两个层次理解。PagedAttention 解决的是一个实例内部怎么分配和管理 KV 显存。Preble 解决的是集群里哪一个实例应该接这个请求。它的收益最容易出现在输入长、前缀重复多、输出相对短的任务里,因为这时路由能决定大量 prefill 是被复用,还是被重复执行。