No Request Left Behind: Tackling Heterogeneity in Long-Context LLM Inference with Medha

📄 arXiv: 2409.17264v5 📥 PDF

作者: Amey Agrawal, Haoran Qiu, Junda Chen, Íñigo Goiri, Chaojie Zhang, Rayyan Shahid, Ramachandran Ramjee, Alexey Tumanov, Esha Choukse

分类: cs.LG, cs.DC

发布日期: 2024-09-25 (更新: 2025-11-26)

💡 一句话要点

Medha：通过细粒度抢占式调度解决长上下文LLM推理中的异构性问题

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 长上下文LLM 推理服务 抢占式调度 异构工作负载 KV-Cache并行

📋 核心要点

  1. 现有LLM serving系统在处理混合短查询和长文档的异构工作负载时，由于注意力机制的二次复杂度，容易出现“车队效应”，导致短请求延迟增加。
  2. Medha通过引入细粒度的抢占式调度，结合自适应分块、流式流水线并行和KV-Cache并行等技术，克服了传统抢占式调度的低效率和扩展性问题。
  3. 实验结果表明，Medha在异构工作负载下，相比现有非抢占式系统，吞吐量提升5.7倍，中位数延迟降低30倍，第99百分位延迟降低174倍。

📝 摘要（中文）

部署百万token级别的大语言模型(LLM)极具挑战，因为生产环境的工作负载高度异构，混合了短查询和长文档。这种异构性，加上注意力机制的二次复杂度，导致严重的“车队效应”，即长时间运行的请求会阻碍短的、交互式的请求，从而降低系统响应速度。我们提出了Medha，一个通过引入细粒度的、抢占式调度到LLM推理的serving系统，以消除这些车队效应。Medha通过一套协同设计的机制使抢占成为可能，包括自适应分块和流式流水线并行，克服了分块的低效率和扩展挑战。此外，我们提出了一种新的并行策略KV-Cache并行，以减少解码延迟，并在非常长的上下文中提供交互性。这些机制由长度感知相对松弛(LARS)调度器协调，这是一种感知截止时间和异构性的调度策略，可防止车队效应和困扰简单策略的饥饿现象。在异构工作负载下，与最先进的非抢占式系统相比，Medha的吞吐量提高了5.7倍，同时中位数和第99百分位延迟分别降低了30倍和174倍。

🔬 方法详解

问题定义：论文旨在解决长上下文LLM推理服务中，由于请求长度差异巨大导致的性能瓶颈问题。现有方法，如非抢占式调度，会导致长请求阻塞短请求，造成严重的“车队效应”，显著增加短请求的延迟，影响用户体验。

核心思路：Medha的核心思路是引入细粒度的抢占式调度，允许系统中断正在处理的长请求，优先处理短请求，从而避免“车队效应”。为了使抢占式调度在LLM推理中可行，论文提出了一系列优化技术，以克服传统抢占式调度的开销和扩展性问题。

技术框架：Medha的整体架构包含以下几个主要模块：1) 自适应分块(Adaptive Chunking)：将长请求分解为更小的块，以便进行抢占和调度。2) 流式流水线并行(Stream Pipeline Parallel)：优化分块请求的处理流程，减少抢占带来的额外开销。3) KV-Cache并行(KV-Cache Parallelism)：一种新的并行策略，用于减少解码延迟，保证长上下文下的交互性。4) 长度感知相对松弛(LARS)调度器(Length-Aware Relative Slack (LARS) scheduler)：根据请求的长度和剩余时间，动态调整调度优先级，防止“车队效应”和“饥饿”现象。

关键创新：Medha的关键创新在于将细粒度的抢占式调度应用于LLM推理服务，并提出了一系列优化技术来克服抢占带来的挑战。与现有方法相比，Medha能够更好地处理异构工作负载，显著降低短请求的延迟，提高系统整体的吞吐量。KV-Cache并行也是一个重要的创新点，它通过并行化KV-Cache的访问，有效降低了解码延迟。

关键设计：LARS调度器是Medha中的关键组件，其核心思想是根据请求的长度和剩余时间（slack）来动态调整优先级。具体来说，LARS调度器会计算每个请求的相对松弛度（relative slack），即剩余时间与请求长度的比值。长度较短且剩余时间较少的请求，其相对松弛度较高，优先级也较高，从而保证短请求能够及时得到处理。自适应分块策略会根据模型和硬件特性动态调整chunk的大小，以平衡抢占开销和调度粒度。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，在异构工作负载下，Medha相比于最先进的非抢占式系统，吞吐量提升了5.7倍，中位数延迟降低了30倍，第99百分位延迟降低了174倍。这些数据充分证明了Medha在处理长上下文LLM推理任务时的优越性能，尤其是在降低尾部延迟方面表现突出。

🎯 应用场景

Medha适用于需要处理大量长上下文LLM推理请求的场景，例如文档总结、代码生成、问答系统等。它可以显著提高系统的响应速度和吞吐量，改善用户体验。该研究对于构建高效、可扩展的LLM serving系统具有重要的指导意义，并有望推动LLM在更多实际应用中的部署。

📄 摘要（原文）

Deploying million-token Large Language Models (LLMs) is challenging because production workloads are highly heterogeneous, mixing short queries and long documents. This heterogeneity, combined with the quadratic complexity of attention, creates severe convoy effects where long-running requests stall short, interactive ones, degrading system responsiveness. We present Medha, a serving system that eliminates these convoys by introducing fine-grained, preemptive scheduling to LLM inference. Medha makes preemption practical with a co-designed set of mechanisms -- including Adaptive Chunking and Stream Pipeline Parallel that overcome the perceived inefficiencies and scaling challenges of chunking. Additionally, we present a new parallelism strategy KV-Cache Parallelism to reduce the decode latency and afford interactivity despite very long context. These mechanisms are orchestrated by a Length-Aware Relative Slack (LARS) scheduler, a deadline and heterogeneity-aware scheduling policy that prevents both the convoy effect and the starvation that plagues simpler policies. Under a heterogeneous workload, Medha improves throughput by 5.7x while reducing median and 99th percentile latency by 30x and 174x, respectively, compared to state-of-the-art non-preemptive systems.