🤖 machine learning

A Queueing-Theoretic Framework for Stability Analysis of LLM Inference with KV Cache Memory Constraints

本文提出了一种新颖的排队论框架，该框架整合了计算与 GPU 内存约束，以推导大语言模型推理的严格稳定性条件，从而实现精准的集群规模规划，并通过真实世界实验验证，其偏差小于 10%。

原作者： Chengyi Nie, Nian Si, Zijie Zhou

发布于 2026-05-07

📖 1 分钟阅读☕ 轻松阅读

原作者： Chengyi Nie, Nian Si, Zijie Zhou

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你经营着一家非常受欢迎的高科技面包店，名叫“大语言模型面包店”。顾客（请求）走进来，要求定制蛋糕（答案）。但这不是一家普通的面包店；它有两条非常具体且棘手的规则，使得经营变得困难。

两大难题

1. “记忆冰箱”（KV 缓存）
在普通面包店里，你烤好一个蛋糕，端给顾客，然后擦干净柜台。但在这家面包店里，每当一位顾客订购蛋糕时，你就必须为迄今为止使用过的每一种原料保留一张特殊的“食谱卡”。

关键点： 在蛋糕制作过程中，你必须将所有这些食谱卡都保存在你的冰箱（GPU 显存）里。
问题所在： 如果同时涌入太多顾客，或者他们订购了巨大而复杂的蛋糕，你的冰箱就会被食谱卡塞满。一旦冰箱满了，即使你的烤箱空着，你也无法接受任何新订单。系统会崩溃。

2. “缓慢的烤箱”（计算）
制作这些蛋糕需要很长时间。你不能一次性把所有蛋糕都烤好；你必须一层一层地烤。

关键点： 如果你试图同时烤太多蛋糕，烤箱就会过载，烘烤速度会慢如蜗牛。
问题所在： 如果顾客到来的速度快于你能烘烤的速度，就会排起长队。如果队伍太长，面包店就失去了作用，因为人们要永远等待。

旧方法与新方法

旧方法：
此前，试图经营这些面包店的人只关注烤箱（计算）。他们认为：“如果我有足够的烤箱，就能应对人群。”他们忽略了冰箱（显存）。这导致了灾难：他们拥有充足的烤箱，但冰箱里塞满了食谱卡，以至于无法烤制任何新蛋糕。

新方法（本文）：
本文的作者构建了一个数学蓝图（排队论框架），同时审视烤箱和冰箱。

他们创造了一个简单的公式，来回答一个重大问题：“我需要购买多少台烤箱（GPU），才能确保我的面包店永远不会不堪重负，同时也不会因购买过多而浪费资金？”

蓝图如何运作

作者意识到，一位顾客的“成本”不仅仅在于烘烤他们所需的时间，还在于他们在整个服务期间，其食谱卡在冰箱中占据的空间。

“生命周期占用”：他们计算了单个顾客从进店到离开期间，总共占用的“冰箱空间”。
稳定性分界线：他们在沙地上画了一条线。
- 线以下：如果顾客数量少于你的冰箱与烤箱组合所能处理的容量，队伍就会保持短小，每个人都能迅速拿到蛋糕。系统是稳定的。
- 线以上：如果顾客涌入过多，冰箱会填满，烤箱会卡住，队伍将无限增长。系统是不稳定的。

现实世界测试

作者们不仅仅在白板上做数学题。他们走进了一家真实的面包店（使用实际的 NVIDIA A100 高端计算机芯片），并测试了他们的蓝图。

结果：他们的公式准确预测了面包店每秒能处理多少蛋糕。
准确性：他们的预测与实际情况极其接近——通常与实际数值相差在**10%**以内。

为何这很重要（根据本文）

这份蓝图为面包店老板（系统操作员）提供了一件可靠的工具。他们不再需要猜测，也不必购买过多昂贵的烤箱（这会浪费资金）或过少的烤箱（这会让顾客生气）；他们可以利用这套数学方法，计算出在特定顾客数量下，保持面包店顺畅运行所需的确切 GPU 数量。

简而言之：本文提供了一本规则手册，用于平衡“烤箱速度”和“冰箱空间”，以确保你的 AI 面包店既不会耗尽空间，也不会陷入无尽的排队困境。

技术摘要：基于排队论的 KV 缓存内存约束下大语言模型推理稳定性分析框架

问题陈述

大语言模型（LLM）的快速普及为大规模高效推理带来了显著挑战。与传统工作负载不同，LLM 推理受到双重瓶颈的制约：计算吞吐量与键值（KV）缓存的内存开销。虽然 KV 缓存通过复用已生成 token 的表示来加速解码，但它消耗了大量 GPU 内存，往往成为主要的容量限制因素。

现有的 LLM 推理排队模型通常侧重于计算限制或将内存视为静态约束，未能捕捉推理过程中计算与内存增长之间的动态相互作用。具体而言，随着请求经过提示（预填充）和 token 生成（解码）阶段，其内存占用呈线性演变。如果请求到达率超过系统的有效服务率（该服务率由 GPU 计算能力和可用 KV 缓存内存共同决定），队列将无限增长，导致系统不稳定、延迟不可接受以及用户体验下降。目前缺乏严谨的理论框架来显式地纳入这些动态内存约束，以确定稳定性条件并指导 GPU 资源分配。

方法论

作者提出了一种新颖的排队论框架，将 LLM 推理建模为受硬 KV 缓存内存约束（ $M$ ）的离散时间、工作守恒排队系统。

1. 系统模型

请求结构：每个请求 $i$ 包含大小为 $s_i$ 的提示和长度为 $o_i$ 的响应，两者从联合分布 $F_{in-out}$ 中采样。
处理阶段：
- 提示阶段：提示按固定大小块（ $\hat{s}$ ）处理。提示第 $j$ 块的内存使用量呈线性增长（ $j \times \hat{s}$ ）。
- 解码阶段：随着 token 按顺序生成，每步内存使用量增加一个 token 的 KV 缓存量。请求完成时，其总内存占用达到 $s_i + o_i$ 。
内存约束：系统必须在所有时刻 $t$ 满足 $\sum_{i \in S(t)} (c_i^{(t)}\hat{s} + d_i^{(t)}) \le M$ ，其中 $S(t)$ 是活跃请求集合， $c_i^{(t)}$ 是已处理的提示块索引， $d_i^{(t)}$ 是已处理的输出 token 索引。
调度：该框架假设采用连续批处理和工作守恒策略（如先到先服务），即服务器在容量允许时处理下一个优先级的提示。

2. 理论推导

作者定义了单个请求的生命周期累积内存使用量 $g(s, o)$ ，代表该请求在整个服务时间内消耗的总内存“面积”。
$g(s, o) := \sum_{k=1}^{s/\hat{s}} k\hat{s} + \sum_{j=1}^{o} (s+j)$
基于此，他们推导出了最大稳定服务率 $\mu$ ：
$\mu = \frac{M}{\bar{b} \mathbb{E}_{s,o \sim p(s,o)}[g(s, o)]}$
其中 $\bar{b}$ 是归一化的批处理时间。

3. 稳定性分析

利用针对 LLM 分段线性内存动力学调整的 Lyapunov 漂移论证，该论文确立了两条关键定理：

不稳定性：如果到达率 $\lambda > \mu$ ，系统过载，请求数量将增长至无穷大。
稳定性：如果 $\lambda < \mu(1 - \delta)$ ，其中 $\delta = \frac{\text{ess sup}(s+o)}{M} \ll 1$ 代表容纳最大单个作业所需的内存松弛量，则系统是稳定的（正递归马尔可夫链）。

主要贡献

新颖建模：本文引入了首个 LLM 推理排队模型，该模型显式集成了计算需求与由 KV 缓存控制的动态 GPU 内存约束。它通过增加内存感知能力并细化带有分块预填充阶段的调度设置，对先前的模型进行了泛化。
严谨的稳定性条件：作者推导出了封闭形式的稳定性和不稳定性条件。这些结果为确定随机工作负载下 LLM 服务系统的最大可持续吞吐量提供了原则性基础。
实证验证：通过在真实 GPU 生产环境（NVIDIA A100）中进行广泛实验，验证了理论预测，涵盖了单 GPU 和多 GPU（数据并行）配置。

实验结果

作者使用 Meta-Llama-3-8B 模型在配备 vLLM 推理引擎的 8-GPU 测试台上进行了实验。

准确性：理论服务率 $\mu_{theory}$ 与实测 GPU 服务率 $\mu_{gpu}$ 高度吻合。在各种提示与解码（P/D）比率（1:1、2:1、1:2）以及真实世界数据集（LongBench v2）下，预测误差（绝对百分比差距）保持在 10% 以内（具体范围为 2.25% 至 8.38%）。
多 GPU 可扩展性：在 8-GPU 集群设置中，理论模型呈线性扩展，预测率与观测率之间的差距仅为 3.38%。
稳定性动态：实验证实，当 $\lambda < \mu$ 时，队列长度保持有界（例如，单 GPU 情况下 $\le 5$ ），而当 $\lambda > \mu$ 时，队列呈线性无界增长。

意义与主张

该论文声称提供了一种用于系统部署和资源分配的有力工具。通过结合估计的请求到达率与推导出的稳定服务率，运营人员可以计算所需的集群规模，以：

避免昂贵的过度采购（闲置 GPU）。
防止违反性能的低配（无界队列和延迟尖峰）。

作者强调，他们的框架为容量规划提供了“原则性基础”，使从业者能够定量地平衡容量与需求。他们指出，虽然当前工作侧重于数据并行部署，但该框架可通过调整有效内存和批处理时间参数扩展至张量并行，尽管流水线并行和分离部署仍需进一步研究。结果证实，将内存动力学纳入排队模型对于现代 LLM 服务系统中的准确稳定性分析至关重要。