Blog Tags GitHub
Back to blog
llm-inference scheduling batching resource-fairness kv-cache competitive-ratio cost-alignment profit-analysis

Efficiency and Cost Alignment in Batched LLM Serving via Resource-Fair Scheduling

Resource-Fair Scheduling 将 LLM 推理中的 batching 外部性形式化为资源公平问题，提出 LJF 和 ISJL 两种公平调度算法，并建立利润分解理论将吞吐量与线性定价下的运营成本对齐

Efficiency and Cost Alignment in Batched LLM Serving via Resource-Fair Scheduling

一、论文概述

项目内容
标题Efficiency and Cost Alignment in Batched LLM Serving via Resource-Fair Scheduling
作者Dayi Yao, Zijie Zhou
论文arXiv:2608.02244
发布2026-08-03
领域LLM 推理系统、调度算法、资源公平性

二、核心思想

问题定义

LLM 推理通过批处理（batching）提升吞吐量，但批处理引入了微妙的外部性（externality）：当长请求与短请求在同一个 batch 中解码时，短请求为长请求”买单”——每步 FLOPs 和 KV 内存占用由 batch 中最长上下文决定。具体而言：

  • 注意力操作：请求 ii 的注意力计算随其 KV 缓存大小 ai(t)a_i^{(t)} 缩放，但 GPU 核并行处理注意力头，墙钟时间约正比于 max⁡i∈S(t)ai(t)\max_{i \in S^{(t)}} a_i^{(t)}（而非总和）
  • 前馈层：对整个 batch 做联合矩阵乘，投影矩阵从 GPU HBM 加载一次，成本近似常数

这两个机制意味着短请求与长请求共批时，付出了与长请求 KV 足迹成比例的延迟。论文将这一现象形式化为资源公平问题，而非通过结果或服务保证定义公平。

FCFS 不公平示例

SJF 不公平示例

FCFS 与 SJF 均违反公平约束：长请求与短请求的 KV 足迹差异可任意放大，短请求被迫为长请求承担延迟。

解决方案概述

论文的核心创新在于：

  1. 定义公平约束：以 batch 内各请求的 KV 缓存足迹（解码进度）作为资源消耗代理
  2. 提出两个公平调度算法：
    • LJF（Longest Job First）：绝对公平（任意 α≥0\alpha \geq 0 满足约束），但吞吐量差
    • ISJL（Insert Short Jobs with Limit）：参数化公平，接受公平性参数 α\alpha，可调公平-吞吐权衡
  3. 理论保证：ISJL 的竞争比下界为 3/43/4，并给出竞争比作为 α\alpha 函数的精确刻画
  4. 经济分析：证明资源公平调度是对齐 token 线性计价收入与 max 驱动的批处理成本的机制

三、技术架构

模型设定

单计算 worker 上的 LLM 推理调度问题。nn 个请求等待处理，请求 ii 由参数 oio_i（输入 prompt 与生成输出的总 token 数）刻画。请求以最多 BB 个为一组批处理。模型采用 token-step 抽象：一个服务步使每个活跃请求前进一个 token。makespan TA(I)T_{\mathcal{A}}(\mathcal{I}) 计数调度步数而非 GPU 毫秒。

核心公式

公平约束（KV 缓存足迹差异）：

max⁡i∈S(t){ai(t)}−min⁡i∈S(t){ai(t)}≤α(1)\max_{i \in S^{(t)}}\{a_i^{(t)}\} - \min_{i \in S^{(t)}}\{a_i^{(t)}\} \leq \alpha \tag{1}

其中 ai(t)∈[0,oi]a_i^{(t)} \in [0, o_i] 为请求 ii 在时间 tt 已生成的解码 token 数。

吞吐量定义：

Throughput(A;I)=∑i=1noiTA(I)(18)\text{Throughput}(\mathcal{A};\mathcal{I}) = \frac{\sum_{i=1}^{n} o_i}{T_{\mathcal{A}}(\mathcal{I})} \tag{18}

竞争比定义：

CR(A)=inf⁡IThroughput(A;I)OPT(I)(16)CR(\mathcal{A}) = \inf_{\mathcal{I}} \frac{\text{Throughput}(\mathcal{A};\mathcal{I})}{\text{OPT}(\mathcal{I})} \tag{16}

算法 1：LJF（Longest Job First）

LJF 以离散 batch 运行：每次选择队列中最长的 BB 个请求同时处理，系统空转直至当前 batch 中最长请求完成，才选择下一批。

  • Proposition 3.1：LJF 对任意 α>0\alpha > 0 满足公平约束（同批请求同时启动，瞬时加速相等）
  • 缺点：直到整个 batch 完成才接收新请求，即使短作业提前释放资源也空转

LJF makespan：

TLJF(I)=o1+oB+1+o2B+1+⋯+o(n−1)B+1(8)T_{\mathcal{L}JF}(\mathcal{I}) = o_1 + o_{B+1} + o_{2B+1} + \dots + o_{(n-1)B+1} \tag{8}

LJF 调度示例

LJF 按长度降序将请求分为 batch，每批等待最长作业完成后才启动下一批。

算法 2：ISJL（Insert Short Jobs with Limit）

ISJL 接受公平性参数 α\alpha，允许有界公平违规（α\alpha 内）以换取显著吞吐提升。

Warm-up case（B=2）两阶段：

  • Phase One（Batch 初始化）：选择最长等待作业 o1o_1，计算阈值 q=min⁡{o1−o2+β,2α}q = \min\{o_1 - o_2 + \beta, 2\alpha\}，优先选择处理时间 ≤q\leq q 的最长作业与 o1o_1 并行
  • Phase Two（Batch 完成）：当资源释放（作业完成或 o2o_2 长度触发）时触发，调度新作业

通用化（B ≥ 2，固定 β=α\beta = \alpha）： 定义 M=min⁡{B,∣{i:oi>α}∣}M = \min\{B, |\{i: o_i > \alpha\}|\}。每个 worker 设置打包预算 capj=min⁡{2α,o1−oj+α}\text{cap}_j = \min\{2\alpha, o_1 - o_j + \alpha\}，贪心分配短作业。两阶段调度：先在各 worker 上运行总长度恰为 α\alpha 的前缀，再运行剩余尾段，保证任何 worker 不超过最慢活跃作业 α\alpha 个单位。

Over/Under Insert 示意

Jigsaw 效应示意

ISJL 的关键挑战是”过度插入”与”欠插入”的权衡，以及短作业跨 batch 的”拼图”（jigsaw）效应。

核心公式（续）

batch 瞬时成本：

CA(t)=c+τ∣S(t)∣max⁡i∈S(t)ri(t)(3)C_{\mathcal{A}}^{(t)} = c + \tau|S^{(t)}|\max_{i \in S^{(t)}} r_i^{(t)} \tag{3}

其中 c≥0c \geq 0 为一步服务固定成本，τ>0\tau > 0 将 max 驱动的资源足迹转换为成本，ri(t)r_i^{(t)} 为请求 ii 当前 KV 足迹。

总成本与利润：

CA(I)=∑t=1TA(I)CA(t),ΠA(I)=R(I)−CA(I)(4)C_{\mathcal{A}}(\mathcal{I}) = \sum_{t=1}^{T_{\mathcal{A}}(\mathcal{I})} C_{\mathcal{A}}^{(t)}, \qquad \Pi_{\mathcal{A}}(\mathcal{I}) = R(\mathcal{I}) - C_{\mathcal{A}}(\mathcal{I}) \tag{4}

batching 外部性（Theorem 5.1）：

EA(I):=∑t=1TA(I)∑i∈S(t)(max⁡j∈S(t)rj(t)−ri(t))(6)E_{\mathcal{A}}(\mathcal{I}) := \sum_{t=1}^{T_{\mathcal{A}}(\mathcal{I})} \sum_{i \in S^{(t)}} \left(\max_{j \in S^{(t)}} r_j^{(t)} - r_i^{(t)}\right) \tag{6}

利润分解定理（Theorem 5.1）：

ΠA(I)=R(I)−τQ(I)−cTA(I)−τEA(I)(7)\Pi_{\mathcal{A}}(\mathcal{I}) = R(\mathcal{I}) - \tau Q(\mathcal{I}) - cT_{\mathcal{A}}(\mathcal{I}) - \tau E_{\mathcal{A}}(\mathcal{I}) \tag{7}

其中 Q(I)=12∑i=1noi(oi+1)Q(\mathcal{I}) = \frac{1}{2}\sum_{i=1}^{n} o_i(o_i+1) 为内在资源项，与调度无关。

公平性 → 外部性界：

EA(I)≤αO(I)(9)E_{\mathcal{A}}(\mathcal{I}) \leq \alpha O(\mathcal{I}) \tag{9}

竞争比作为 γ=α/o1\gamma = \alpha/o_1 的函数：

CR(γ)={1+γ1+2γ,0<γ≤12,2−γ3−2γ,12<γ<1(10)\mathrm{CR}(\gamma) = \begin{cases} \dfrac{1+\gamma}{1+2\gamma}, & 0 < \gamma \leq \tfrac{1}{2}, \\[4pt] \dfrac{2-\gamma}{3-2\gamma}, & \tfrac{1}{2} < \gamma < 1 \end{cases} \tag{10}

竞争比作为 \gamma 的函数

竞争比在 γ≤1/2\gamma \leq 1/2 时递减，在 1/2<γ<11/2 < \gamma < 1 时递增，最大值 3/43/4 出现在 γ=1/2\gamma = 1/2。

四、核心创新

创新点说明理论/实验依据
资源公平形式化首次将 LLM 批处理的 batching 外部性形式化为资源公平问题KV 足迹差异约束 (1)
LJF 算法绝对公平调度，作为最差吞吐量基准Proposition 3.1
ISJL 算法参数化公平调度，可调公平-吞吐权衡竞争比下界 3/43/4（Theorem 3.19）
竞争比精确刻画竞争比作为 α\alpha 的分段函数Section 4 三类型对抗实例分析
利润分解定理分离收益、内在资源、时间成本、外部性四项Theorem 5.1
非 clairvoyant 扩展移除作业长度已知假设，支持预测区间Section 3.4

五、代码实现分析

论文为理论驱动研究，通过模拟实验验证，无开源代码。实验设置：

经济实验（Section 5）

  • 线性定价：pi=ρ0oip_i = \rho_0 o_i，token 计价收入与调度无关
  • 实例规模：n=400n = 400, B=50B = 50
  • 成本模型：CA(t)=c+τ∣S(t)∣max⁡iri(t)C_{\mathcal{A}}^{(t)} = c + \tau|S^{(t)}|\max_i r_i^{(t)}

系统效率实验（Section 6）

  • 数据集：LMSYS-Chat-1M 抽取 2,000 条对话
    • 均值 126 tokens、中位数 90、最大值 905、方差 14938
  • 算法对比：FCFS、SJF、LJF、ISJL(α=50,100,150\alpha = 50, 100, 150)
  • 批大小：B=16B = 16, B=32B = 32
  • 指标：吞吐量 + 平均端到端延迟（AEL）

Token 长度分布

LMSYS-Chat-1M 抽取样本的 token 分布高度偏斜：多数请求较短（中位数 90），但长尾请求（最大 905）在批处理中造成外部性。

六、实验结果

Table 1：利润与成本分解（线性定价，n=400, B=50）

策略ProfitCostτQ\tau QcTcTτE\tau E吞吐提升平均违规
FCFS128.7368.4132.071.2435.10-0.12%566.26
LJF163.8233.3132.071.240.000.00%0.00
ISJL(α=50)162.5334.6032.071.201.333.50%36.62
ISJL(α=100)161.1036.0332.071.162.796.21%74.83
ISJL(α=150)159.5937.5532.071.124.3510.48%111.86
ISJL(α=250)156.3040.8332.071.057.7117.97%187.29
ISJL(α=400)151.3145.8332.071.0212.7421.42%290.71
ISJL(α=500)147.8249.3232.071.0116.2322.03%361.91

关键发现：τQ\tau Q 恒定（与调度无关），利润差异完全来自 cTcT（时间成本）和 τE\tau E（外部性成本）的权衡。ISJL 用外部性换取吞吐提升，小 α\alpha 时利润接近 LJF。

成本分解对比

利润-吞吐前沿

Table 2：ISJL 相对 LJF 的盈亏平衡开销

α时间节省 vs LJFτEISJL(α)\tau E_{ISJL(\alpha)}cα⋆c_\alpha^\star
5083.21.350.0162
100147.62.810.0190
150235.24.360.0185
250380.07.710.0203
300414.09.330.0225
500444.216.250.0366

盈亏平衡解读：ISJL 相比 LJF 的时间节省随 α\alpha 增长，但外部性成本 τE\tau E 也上升。当单位时间成本 cc 超过阈值 cα⋆c_\alpha^\star 时，ISJL 的利润才超过 LJF——为运营者提供决策准则。

ISJL 与 LJF 利润差

Table 3：不同调度算法的吞吐量与 AEL

批大小指标FCFSSJFLJFISJL(α=50)ISJL(α=100)ISJL(α=150)
B=16吞吐量216196243262270276
B=16AEL626066535654
B=32吞吐量278259323357369378
B=32AEL706778626365

关键发现：ISJL 在所有设置下优于 FCFS、SJF、LJF，吞吐量提升 13%~21%，同时降低平均延迟。

七、相关工作

LLM 推理系统

  • vLLM (Kwon et al. 2023)：PagedAttention、显式 KV 内存管理、跨异构请求构建 batch
  • Sarathi-serve (Agrawal et al. 2023)：chunked prefill、均匀微批
  • DistServe、Splitwise：P/D 分离

批处理与序列长度敏感性

  • Sheng et al. 2024、Khan et al. 2024、Wei et al. 2025：测量 decode 阶段 GPU 利用率低、对序列长度敏感、均匀微批的收益
  • 论文将这些观察形式化为资源公平问题

在线/离线调度理论

  • Jaillet et al. 2025、Wang et al. 2025：离线调度中作业长度已知假设
  • LJF/ISJL 类比经典调度理论中的 LPT、SRPT 等算法

八、总结

核心贡献

  1. 资源公平形式化：首次将 LLM 批处理的 batching 外部性定义为基于 KV 足迹的资源公平问题
  2. LJF 算法：绝对公平调度，最差吞吐量基准
  3. ISJL 算法：参数化公平-吞吐权衡，竞争比下界 3/43/4
  4. 竞争比精确刻画：竞争比作为 α\alpha 的分段函数
  5. 利润分解定理：将 token 线性收入与 max 驱动批成本对齐

技术影响

  • 为 LLM 服务中的调度问题提供了理论框架
  • 公平约束（KV 足迹差异）可直接用于实际调度器设计
  • 利润分解为运营者在吞吐与公平之间权衡提供了量化工具

局限性

  • 采用 token-step 抽象，未建模 GPU 墙钟时间的复杂关系
  • 主分析假设作业长度已知（已扩展非 clairvoyant 设置）
  • 单 worker 模型，未考虑分布式/多节点场景
  • 实验为模拟驱动，未在真实 LLM 推理系统部署

九、参考资源