LLM Serving Optimization with Variable Prefill and Decode Lengths

技术摘要：具有可变预填充与解码长度的 LLM 服务优化

问题定义
本文研究了在具有固定键值（KV）缓存内存预算的单个计算工作节点上，针对大语言模型（LLM）推理的离线调度问题。系统处理在 $t=0$ 时刻同时到达的 $n$ 个请求。每个请求 $i$ 的特征由异构的提示词长度（预填充大小，$s_i$）和响应长度（解码大小，$o_i$）组成。

核心挑战源于自回归解码过程中动态变化的内存消耗。在预填充阶段，内存消耗与 $s_i$ 成正比；而在解码阶段，内存消耗随生成的每个 token 线性增长（对于第 $j$ 个 token，为 $s_i + j$）。因此，一个工作节点能够同时处理的并发请求数量会随着活跃请求的生成进度而动态波动。目标是在满足任何时间步内聚合内存使用量不超过容量 $M$ 的约束下，最小化总端到端延迟（Total End-to-End Latency, TEL），即所有请求完成时间的总和。

作者放宽了先前研究（Jaillet et al., 2025）中关于均匀输入大小的假设，考虑了一个更符合现实的场景，即工作负载混合了短对话提示词与长文档摘要任务。

理论发现与挑战
本文确立了放宽均匀输入大小假设从根本上改变了调度问题的复杂性：

1. NP 难解性： 通过对受限 3-Partition 问题的归约，证明了具有异构 $s_i$ 和 $o_i$ 的广义调度问题是 NP 难的。
2. 标准启发式算法的失效： 研究表明，包括先来先服务（FCFS）、最短输出优先（MC-SF）以及基于总规模的优先级排序在内的标准策略，在这种异构设置下的近似比是无界的。具体而言，一个具有大输入但小输出的请求可能会在短时间内消耗大量内存，而一个具有小输入但长输出的请求可能会占用内存很长时间，这种权衡是简单的启发式算法无法解决的。

方法论：Sorted-F 算法
为了应对这些挑战，作者提出了 Sorted-F，一种旨在实现常数因子近似保证的调度算法。该算法分为两个阶段运行：

1. 批次构建（阶段 1）： 算法迭代地选择可行的请求批次以形成一个有序列表。选择过程由一种新颖的质量度量 $F(X)$ 指导，其中 $F(X)$ 是针对请求集 $X$ 定义的：
   $$F(X) = \frac{\sum_{r_i \in X} o_i}{|X|^2}$$
   该度量平衡了批次大小（$|X|$）与聚合下游解码成本（$\sum o_i$）。最小化 $F(X)$ 等同于最大化“吞吐量密度”（即单位平均解码时间内完成的请求数）。在每个选定的批次内，请求按非递减的输出长度进行排序。
2. 执行（阶段 2）： 系统在离散时间步内执行调度，只要满足内存可行性约束，就将有序列表中的请求引入当前批次，并利用连续批处理（continuous batching）以及预填充/解码混合技术。

近似保证
作者证明了 Sorted-F 相对于最优离线调度方案实现了至多 48 的常数近似比。其证明涉及一系列结构化变换（分离、分组和对齐），将 Sorted-F 调度方案和最优调度方案转换为可比较的形式，从而证明了每一步的延迟增加都被限制在一个常数因子之内。

实际实现
考虑到在大型 $n$ 规模下进行阶段 1 的组合优化计算成本过高，本文提出了三种实用的求解器：

• 精确动态规划： 为小规模实例（$n \le 100$）提供精确解，复杂度为 $O(n^2 M)$。
• 局部交换搜索（Local Swap Search）： 一种针对中等规模（$n \le 500$）的启发式算法，通过成对交换（$O(n^2)$）不断改进初始贪婪解。
• 分位数贪婪选择（Quantile Greedy Selection）： 一种针对大规模系统（$n \ge 1000$）的线性时间启发式算法，利用统计采样过滤异常值并贪婪地填充容量。

此外，本文还引入了 Sorted-LP，一种利用线性规划（LP）松弛解来对请求进行排序的启发式算法，以及 Sorted-F+Amin，一种自适应变体，通过在推理过程中动态细化估计，处理输出长度的预测不确定性。

实验结果
在混合工作负载（结合了 LMSYS-Chat 数据集和 Arxiv 长文档摘要）上的数值实验表明：

• 延迟降低： 使用局部交换搜索的 Sorted-F 在性能上持续优于 FCFS、MC-SF 以及 LP 引导的基准算法。在包含 2000 个请求的 80/20 短/长混合负载中，与 FCFS 相比，Sorted-F 将平均延迟降低了 4.87 倍；与 MC-SF 相比，降低了 2.09 倍。
• 最优间隙（Optimality Gap）： 在可处理的实例中，Sorted-F 与 LP 松弛下界之间的经验差距很小（约为 1.03–1.09），这表明尽管理论界限较宽，但在实践中该算法的表现接近最优。
• 工作负载敏感性： Sorted-F 的优势在异构且过载（内存成为约束条件）的场景中最为显著。在同构或轻负载场景下，其优势有所减弱。
• 在线性能： 在泊松到达机制下测试的后退时域（receding-horizon）变体（Sorted-F-Online）在过载在线场景中较 MC-SF 和 FCFS 有显著改进，但在稳定的低延迟场景中收益较小。

意义与主张
本文主张，可变的预填充长度并非微小的建模细节，而是导致标准调度启发式算法失效并使问题变为 NP 难的核心因素。其主要贡献是 Sorted-F 算法，它提供了在异构输入/输出约束下实现 LLM 调度的第一个具有常数因子近似保证的算法。这项工作弥合了理论调度极限与实际 LLM 服务之间的鸿沟，提供了一个可扩展的、具备内存感知能力的框架，能够在无需完美预测输出长度的情况下，显著降低混合工作负载场景下的延迟。作者强调，虽然理论界限为 48，但实验结果表明，在现实设置中，该算法的表现远优于此理论值，更接近最优解。