Semi-Clairvoyant Scheduling of Speculative Decoding Requests to Minimize LLM Inference Latency

📄 arXiv: 2505.17074v1 📥 PDF

作者: Ruixiao Li, Fahao Chen, Peng Li

分类: cs.CL, cs.AI, cs.LG

发布日期: 2025-05-20

💡 一句话要点

提出LAPS-SD算法，通过半先知调度优化推测解码中的LLM推理延迟

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture) 支柱九：具身大模型 (Embodied Foundation Models)

关键词: LLM推理 推测解码 请求调度 推理延迟 半先知调度

📋 核心要点

  1. 现有LLM推理调度方法依赖预测输出长度估计执行时间，忽略了token接受率的影响，导致调度不准确。
  2. LAPS-SD算法通过维护多个优先级队列，并允许请求抢占，自适应地根据token接受率动态调度请求。
  3. 实验结果表明，LAPS-SD算法相比现有最优调度方法，能够将LLM推理延迟降低约39%。

📝 摘要（中文）

推测解码通过使用小型推测模型（SSM）生成多个候选token，并使用大型语言模型（LLM）并行验证它们，从而加速LLM推理。这种技术已被广泛集成到LLM推理服务系统中。然而，推理请求通常表现出不确定的执行时间，这给在这些系统中有效调度请求带来了重大挑战。现有工作仅基于预测的输出长度来估计执行时间，这可能不准确，因为执行时间取决于输出长度和LLM验证的token接受率。本文提出了一种半先知请求调度算法，称为用于推测解码的最小已达到/感知服务（LAPS-SD）。给定多个推理请求，LAPS-SD可以通过根据解码期间的特征自适应地调度请求来有效地最小化平均推理延迟。当token接受率是动态的且执行时间难以估计时，LAPS-SD维护多个优先级队列，并允许跨不同队列的请求执行抢占。一旦token接受率变得稳定，LAPS-SD就可以准确地估计执行时间并相应地调度请求。大量实验表明，与最先进的调度方法相比，LAPS-SD将推理延迟降低了约39%。

🔬 方法详解

问题定义：论文旨在解决推测解码中，由于LLM推理请求执行时间不确定，导致难以有效调度请求，从而影响整体推理延迟的问题。现有方法主要依赖预测输出长度来估计执行时间，但忽略了token接受率的影响，导致估计不准确，调度效率低下。

核心思路：论文的核心思路是设计一种半先知调度算法，该算法能够根据解码过程中的token接受率动态调整请求的优先级和调度策略。在token接受率不稳定时，采用基于已完成服务时间和感知服务时间的调度策略，允许请求抢占；在token接受率稳定后，则可以更准确地估计执行时间，从而进行更有效的调度。

技术框架：LAPS-SD算法维护多个优先级队列，每个队列对应不同的优先级。请求最初被分配到默认队列，然后根据其执行情况（已完成服务时间和感知服务时间）在队列之间迁移。当token接受率不稳定时，算法允许高优先级队列中的请求抢占低优先级队列中的请求。当token接受率稳定后，算法可以根据估计的执行时间进行调度。整体流程包括请求入队、优先级队列管理、请求调度和执行、以及请求出队等环节。

关键创新：LAPS-SD算法的关键创新在于其半先知特性，即在调度过程中，算法能够根据已知的token接受率信息动态调整调度策略。这种自适应调度策略能够有效地应对LLM推理请求执行时间的不确定性，从而提高调度效率。与现有方法相比，LAPS-SD算法不仅考虑了输出长度，还考虑了token接受率，从而更准确地估计执行时间。

关键设计：LAPS-SD算法的关键设计包括：1) 优先级队列的数量和优先级分配策略；2) 请求在队列之间迁移的规则，例如基于已完成服务时间和感知服务时间的阈值；3) 请求抢占的条件和机制；4) 当token接受率稳定时，估计执行时间的模型和参数。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，LAPS-SD算法在降低LLM推理延迟方面具有显著优势。与最先进的调度方法相比，LAPS-SD算法能够将推理延迟降低约39%。该结果验证了LAPS-SD算法的有效性，并表明其在实际应用中具有重要的价值。

🎯 应用场景

该研究成果可应用于各种LLM推理服务系统，尤其是在需要处理大量并发请求且请求执行时间不确定的场景下。例如，在线问答系统、文本生成服务、机器翻译服务等。通过采用LAPS-SD算法，可以显著降低推理延迟，提高用户体验，并提升系统的整体吞吐量。

📄 摘要（原文）

Speculative decoding accelerates Large Language Model (LLM) inference by employing a small speculative model (SSM) to generate multiple candidate tokens and verify them using the LLM in parallel. This technique has been widely integrated into LLM inference serving systems. However, inference requests typically exhibit uncertain execution time, which poses a significant challenge of efficiently scheduling requests in these systems. Existing work estimates execution time based solely on predicted output length, which could be inaccurate because execution time depends on both output length and token acceptance rate of verification by the LLM. In this paper, we propose a semi-clairvoyant request scheduling algorithm called Least-Attained/Perceived-Service for Speculative Decoding (LAPS-SD). Given a number of inference requests, LAPS-SD can effectively minimize average inference latency by adaptively scheduling requests according to their features during decoding. When the token acceptance rate is dynamic and execution time is difficult to estimate, LAPS-SD maintains multiple priority queues and allows request execution preemption across different queues. Once the token acceptance rate becomes stable, LAPS-SD can accurately estimate the execution time and schedule requests accordingly. Extensive experiments show that LAPS-SD reduces inference latency by approximately 39\% compared to state-of-the-art scheduling methods.