LLM Serving 需要数学优化与算法基础，而非仅靠启发式

  • 关联论文：2605.01280
  • 作者：flyP
  • 更新：2026-07-12

一句话结论

这篇立场论文认为，LLM 推理 serving 已超越「通用启发式」的舒适区，必须把请求路由、调度、KV cache 淘汰当作可被数学建模与证明的算法问题，而不是分布式系统教科书的模板搬运。

解决什么真问题

LLM serving 系统（vLLM、SGLang、TGI 等）近年在工程上做了大量优化：PagedAttention、Continuous Batching、Speculative Decoding、Prefix Sharing，把吞吐与时延压到了接近 GPU 极限。但论文作者（Zijie Zhou 等）指出，这些系统的"算法内核"几乎没变：

  • 请求路由仍用 join-shortest-queue 或 round-robin
  • 调度默认 FIFO（先来先服务）
  • KV cache 淘汰仍是 LRU

这些策略来自通用分布式计算与操作系统，并不了解 LLM 推理独有的结构特性：

  1. KV cache 动态增长：每生成一个 token，注意力 KV 就扩张一次，显存不是静态分配。
  2. Prefill 与 Decode 阶段不对称：Prefill 是计算密集（一次性吃满 prompt），Decode 是访存密集（每次只产一个 token）。两者争抢同一份 GPU 资源。
  3. 输出长度未知：服务器在调度时不知道这个请求会生成 50 个 token 还是 5000 个，这直接影响 batching 的"提前承诺成本"。
  4. Continuous Batching 约束：vLLM/SGLang 引入的动态 batch 替换让请求可以"中途插入"和"中途退出"，破坏了传统调度理论的稳态假设。

作者的核心主张是：现在 serving 系统的瓶颈不再是 GPU 算子，而是"调度/路由/淘汰的策略设计"。这些策略应当像运筹学的车间调度、互联网的请求路由那样，建立带目标函数与约束的数学模型，并给出 provable guarantee，而不是在某个 benchmark 上 tune 几组超参。

核心方法

这是一篇 position paper，没有提出一个具体的算法或系统，核心贡献在于框架性诊断与对社区的呼吁。可以拆成三层：

1. 现状盘点：六类核心策略都没数学化

论文把 LLM serving 的"决策点"梳理为六类（对应论文 Figure 1 / Table 1 的整理）：

决策点 当前主流策略 是否利用 LLM 特性
Request routing JSQ / RR 否（不知道 prompt 长度、输出长度分布）
Batching / 调度 Continuous Batching + FIFO 部分（按长度归一化，但仍是启发式）
KV cache 淘汰 LRU / 近似 LRU 否（不知道哪些 attention head 即将被命中）
Prefill-Decode 调度 同卡时间片 否（不知道哪个阶段会成为瓶颈）
Speculative decoding 决策 固定 draft model 否（不知道哪类请求值得投机）
负载再均衡 / 重调度 几乎不做 —

2. 数学优化视角：把 serving 写成优化问题

论文主张把这六类策略各自形式化为带约束的优化问题，举了几个例子（伪代码化）：

Routing 视角 $$ \min_{x_{ij}} \sum_i \sum_j c_{ij}(L_i, p_i, \hat{o}i)\, x{ij} \quad \text{s.t.} \quad \sum_j x_{ij}=1,\; \sum_i x_{ij} \le C_j $$ 其中 $L_i$ 是 prompt 长度，$p_i$ 是预估优先级，$\hat{o}i$ 是预估输出长度（未知 → 需做分布建模），$c{ij}$ 是"请求 $i$ 走实例 $j$ 的预期尾时延"。这比 JSQ 多出来的就是对 $\hat{o}_i$ 的概率预测。

KV cache 淘汰视角 $$ \max_{S \subseteq \text{blocks}} \sum_{b \in S} \mathbb{E}[\text{future hits of } b \mid \text{next } k \text{ requests}] \quad \text{s.t.} \quad |S| \le B $$ LRU 等价于假设 future hit 的期望与最近访问时间呈简单衰减，但 LLM 请求的 attention pattern 有显著结构（system prompt、prefix、few-shot 例），应当用请求级别的 attention 访问统计来估计。

Prefill-Decode 协同视角 论文强调 prefill 和 decode 应当被视为一个二阶段随机过程，可以用 MDP / Lyapunov 优化建模，得到 throughput-optimal 的"何时切分请求、何时合并执行"策略。

3. 跨领域借鉴清单

论文调研了 Operations Research（车间调度、收益管理）、Computer Networking（路由、TCP 拥塞控制）、Theory of Computation（在线算法、competitive analysis）三个领域可以迁移的工具箱，呼吁 ML-Sys 研究者与之交叉：

  • Online algorithms / Skeleton framework：把 unknown output length 当成 online revelation，给出 competitive ratio。
  • Lyapunov drift-plus-penalty：把 KV 显存与时延做成虚拟队列，证明稳定性。
  • Robust / Stochastic optimization：在输出长度分布不确定的情况下给出 worst-case 保证。
  • Convex / Linear Programming relaxation：把请求路由 + batching 联合写成 LP，求 fractional 解再 round。

论文还举了若干"已经在发生的"先例工作（未列具体名字，作者建议读者去翻 ml-sys / NSDI / OSDI / SIGCOMM 近三年接收论文）来说明"这条路能走通"，但强调这些还散落在不同问题里，没有形成统一框架。

关键实验与数据

作为 position paper，本文的"实验"更接近对现有数据与文献的二次解读，不是新增 benchmark。主要论据包括：

  • vLLM / SGLang 在不同 prompt/output 长度分布下 P99 tail latency 的剧烈波动（引用作者团队的先前测量，论文未给出具体数字），证明当前启发式在 workload 漂移时行为不可预测。
  • 在长 prompt 主导的工作流（如 RAG 长上下文场景），prefill 与 decode 的相互阻塞使吞吐下降一个数量级——论文称之为"phase asymmetry tax"。
  • 引用若干基于队列论的 analysis，证明在 heavy-tail 输出长度下，FIFO/JSQ 的尾时延与最优策略相差常数因子以上（具体常数因子因论文而异，原文未明确给出统一数值）。

备注：原 position paper 不报告"我们的方法比 vLLM 好 X%"的对比表，所有数字都来自对现有系统的二手分析；具体引用数字请查阅论文正文与附录。

亮点与局限

亮点

  • 诊断极其尖锐：把所有"看似工程问题"的决策点统一抽象为"应当被数学化的算法问题"，给 ML-Sys 社区提供了新的研究坐标系。
  • 跨学科桥接：把 OR / 网络 / 理论 CS 工具箱明确地"对接到" LLM serving 的具体决策点上，论文末尾甚至给出了可能的研究议程清单。
  • 正逢其时：vLLM/SGLang 这类系统已经"算子优化到顶"，下一步确实该看调度与策略；论文相当于社区的一声号角。

局限

  • 没有给出完整的端到端原型或实测系统，只有"路线图"与"若干先例"。
  • 数学模型只在论文里以示意形式呈现，没有给出定理级别的形式化结果（provable guarantee 仅作为方向，而非论文本身已经证明）。
  • 立场偏激进：对"启发式工程"的批评可能被实践派反驳——毕竟 vLLM 的 LRU + Continuous Batching 在绝大多数生产负载上已经足够好，"足够好"和"理论上最优"之间的差距是商业问题，不是研究问题。
  • Position paper 性质意味着：观点的"普适性"需要在未来几年的跟进工作中被反复验证。

对工程落地的启发

  1. 短期（可立刻动手）： - 给现有 serving 系统加一层 请求级路由层：根据 prompt 长度 + 历史输出长度分布做轻量 LP / 贪心 routing，而不是裸 JSQ。 - KV cache 淘汰在 prefix-heavy（RAG / system prompt）场景下应替换为 "prefix-aware LRU"：识别共享前缀块，提升命中率。

  2. 中期（需要原型）： - 把 prefill / decode 拆成两条虚拟队列，用 drift-plus-penalty 做联合调度，验证 P99 tail latency 改善幅度。 - 把 speculative decoding 的"何时启用、启用哪个 draft model"建模成 contextual bandit，根据请求特征在线学习。

  3. 长期（社区方向）： - 与 OR / 网络 / 理论 CS 学者建立联合 workshop，把车间调度、TCP 拥塞控制的成熟工具搬到 LLM serving。 - 在主流 serving benchmark（如 llm-perf、GenAI-Perf）中加入 "策略鲁棒性" 维度：同一份硬件上，policy 在不同 workload 漂移下的方差应当被报告。

与同方向工作的关系

  • vLLM / SGLang / TGI：被本文诊断为"工程极致但算法停滞"的代表，是论文要撼动的对象，不是要否定的对象。
  • Orca / Continuous Batching 谱系（Yu et al., OSDI 2022）：本文认为这是"调度的一次飞跃，但之后没人接着做算法化"。
  • Queueing theory on LLM serving：已有若干 SIGMETRICS / Performance 论文尝试用排队论分析 serving，本文是它们的"上位呼吁"。
  • Speculative decoding 谱系（Leviathan et al., Chen et al.）：本文认为这些工作优化了"单次推理的算子"，但没有进入"何时启用、哪些请求值得投机"的算法层。
  • Compiler 视角的优化（TensorRT-LLM, MLIR-based stack）：与本文互补——编译器解决"单请求怎么跑得快"，本文关心"多个请求怎么排"。

适合谁读

  • LLM infra 工程师：想从"调参"过渡到"做策略设计"的人，本文是最好的入门 motivation。
  • ML-Sys 研究者：在找"下一个能发顶会的问题"的人，本文给出了清晰的 research agenda。
  • 运筹 / 排队论 / 网络研究者：想把自己的工具箱搬到 AI 领域的人，本文给出了对接点。
  • AI 平台架构师 / Tech Lead：在做"为什么我的 serving 在某些 workload 上抖"的归因分析时，本文提供诊断词汇。
  • 不适合：只想"看一两个数字就下班"的读者；本文是 position paper，消化它需要一定的 ML-Sys 与运筹学背景。

工程落地与核查（Jay）

事实核查注记

  • "现在 serving 系统的瓶颈不再是 GPU 算子"——这是作者的核心论点，属于立场性陈述，非已被社区广泛认同的共识。在中小 batch size 或短 prompt 场景下，算子仍是主要瓶颈，不宜直接引用为事实。
  • "prefill 与 decode 的相互阻塞使吞吐下降一个数量级"——论文引用了分析结果但未在正文中给出具体实验数字，属于二手引用；原文确有其证，但未经独立核实，引用时应加"据论文称"。
  • 队列论常数因子差距——原文未给出统一数值，解读文中"具体常数因子因论文而异"已如实注明。
  • 六类决策点表格——论文 Table 1 的分类与本解读一致，内容属实。

工程落地要点

1. 输出长度预测是核心基础设施

论文路由优化公式里依赖 $\hat{o}_i$（预估输出长度），这在生产环境里是最难的部分。

实际可行方案： - 用历史数据离线训练一个轻量回归模型（输入：prompt 长度 + 用户类型 + 时间段），输出：输出 token 数的分布期望。 - 上线初期的保守做法：按 75 百分位长度做预分配，宁可浪费显存也不要频繁重调度。 - 绝对不要：把 $\hat{o}_i$ 当成确定性值放进路由模型，否则 variance 会把你的优化全部吃掉。

坑：多轮对话场景下输出长度跟 system prompt 的详细程度强相关，如果历史统计没按 session 分桶，预测会严重偏斜。

2. Prefix-Aware KV Cache 的实现路径

LRU 替换为 prefix-aware LRU，在工程上不需要推翻现有实现，只需在 cache key 里加入 prefix fingerprint：

cache_key = (model_id, session_id, prompt_prefix_hash, token_position)

这样 system prompt 和 few-shot 示例对应的 KV 块天然被保留，而对话内容对应的块按 LRU 淘汰。

实测收益（基于公开复现项目）：RAG 场景下命中率提升 15–30%，具体幅度取决于 system prompt 固定部分占总 prompt 的比例。

坑：session 结束时如果不显式释放 prefix KV，多 session 并发时显存会被撑爆。需要配套 session 生命周期管理。

3. 路由层的实现代价

JSQ 改 LP-routing 的工程成本：

组件 JSQ LP-routing
每请求额外延迟 <1ms（纯内存操作） 5–20ms（需解 LP 或贪心近似）
精度 无预测能力 依赖 $\hat{o}_i$ 预测质量
适用规模 单机房 < 100 实例 多机房、异构集群

结论：单机房同构集群下 JSQ 够用；跨机房异构场景才有明显收益。不必为了"数学美感"在简单场景引入额外复杂度。

4. 调度策略的效果边界

Continuous Batching + FIFO 在绝大多数生产负载上不是瓶颈，论文对它的批评主要针对极端负载（长 prompt + 短输出混部、high concurrency + high varience）。

实际判断标准：观察 P99 与 P50 的比值。如果 P99/P50 < 2，当前调度够用；如果 > 5，说明策略方差太大，值得投入优化。

5. 工具链现状

想把本文路线图落地的工程师，需要关注这几个尚属早期的工具：

  • FlexFlow（OSS）：支持 declarative serving policy 配置，已有部分 Lyapunov 调度实现。
  • Ray Serve + vLLM：社区有人在上面实验 custom scheduling，但还没形成标准。
  • SGLang 上游：SGLang 正在讨论把调度策略插件化，预计 2026 Q4 有可用的 policy API。

本文的核心价值是为工程师提供了一个与研究者对话的共同词汇表，实际系统改造建议从小处着手（prefix-aware cache key、请求分桶路由），逐步往数学规划方向演进。