🤖 machine learning

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

本論文は、LLM 推論のための厳密な安定性条件を導出するために計算と 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生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

非常に人気のあるハイテクベーカリー「The Large Language Model Bakery」を運営していると想像してください。顧客（リクエスト）がカスタムケーキ（回答）を求めて店内に入ります。しかし、このベーカリーは普通のものではなく、運営を困難にする2 つの非常に具体的で厄介なルールがあります。

2 つの大きな問題

1. 「メモリー冷蔵庫」（KV キャッシュ）
普通のベーカリーでは、ケーキを焼き、提供し、カウンターをきれいに拭きます。しかし、このベーカリーでは、顧客がケーキを注文するたびに、これまでに使ったすべての材料に対する特別な「レシピカード」を保管しなければなりません。

落とし穴: ケーキが作られている間、これらすべてのレシピカードを冷蔵庫（GPU メモリ）に保管し続けなければなりません。
問題点: 一度に顧客が多すぎたり、巨大で複雑なケーキを注文されたりすると、冷蔵庫がレシピカードでいっぱいになります。冷蔵庫がいっぱいになると、オーブンが空いていても新しい注文を受け付けられなくなります。システムがクラッシュします。

2. 「遅いオーブン」（計算）
これらのケーキを作るには時間がかかります。一度にすべてを焼くことはできず、層ごとに焼かなければなりません。

落とし穴: 一度に焼きすぎようとすると、オーブンが過負荷になり、焼き進みが極端に遅くなります。
問題点: 顧客が焼く速度よりも速く来店し続けると、列ができてしまいます。列が長くなりすぎると、人々が永遠に待つことになるため、ベーカリーは役に立たなくなります。

旧来の方法 vs 新しい方法

旧来の方法:
以前、これらのベーカリーを運営しようとする人々は、オーブン（計算）だけを見ていました。「オーブンが十分あれば、混雑に対処できる」と考えていたのです。彼らは冷蔵庫（メモリ）を無視しました。その結果、オーブンは十分にあったものの、冷蔵庫がレシピカードで埋め尽くされて新しいものを焼けなくなるという災害が発生しました。

新しい方法（この論文）:
この論文の著者たちは、オーブンと冷蔵庫の両方を同時に見る数学的な設計図（待ち行列理論に基づくフレームワーク）を構築しました。

彼らは、1 つの大きな疑問に答えるための単純な数式を作成しました。「ベーカリーが圧倒されることなく、かつ無駄にオーブン（GPU）を買いすぎないために、何台のオーブン（GPU）を購入すればよいか？」

設計図の仕組み

著者たちは、顧客の「コスト」が単に焼く時間だけではないことに気づきました。それは、顧客が来店してから退店するまでの全期間を通じて、冷蔵庫のどの程度のスペースをレシピカードが占有するかです。

「生涯の足跡」: 顧客が来店してから退店するまで、1 人の顧客が使用する冷蔵庫のスペースの総量を計算しました。
安定のライン: 彼らは砂にラインを引きました。
- ラインより下: 冷蔵庫とオーブンの組み合わせが処理できる数よりも少ない顧客であれば、列は短く保たれ、誰もがすぐにケーキを受け取れます。システムは安定しています。
- ラインより上: 顧客が多すぎると、冷蔵庫がいっぱいになり、オーブンが詰まり、列が無限に伸びます。システムは不安定です。

実世界でのテスト

著者たちはホワイトボード上で数学を行うだけでなく、実際のベーカリー（NVIDIA A100 GPU と呼ばれる実際のハイエンドコンピュータチップを使用）に入り、設計図をテストしました。

結果: 彼らの数式は、1 秒間にベーカリーが処理できるケーキの数を正確に予測しました。
精度: 彼らの予測は現実と非常に近く、通常は実際の数値の10% 以内でした。

なぜこれが重要なのか（論文によると）

この設計図は、ベーカリーのオーナー（システム運用者）に信頼できるツールを提供します。推測をしたり、高価なオーブンを買いすぎてお金を無駄にしたり、逆に買いすぎて顧客を怒らせたりするのではなく、この数学を使って、特定の数の顧客に対してベーカリーを円滑に運営するために必要なGPU の正確な数を計算できます。

要約すると: この論文は、「オーブンの速度」と「冷蔵庫のスペース」のバランスを取るためのルールブックを提供し、AI ベーカリーがスペース不足になったり、無限の列に巻き込まれたりしないように保証します。

技術的サマリー：KV キャッシュメモリ制約下における LLM 推論の安定性分析のための待ち行列理論的枠組み

問題定義

大規模言語モデル（LLM）の急速な普及は、大規模な推論の効率化に重大な課題をもたらしている。従来のワークロードとは異なり、LLM 推論は計算スループットとキー・バリュー（KV）キャッシュのメモリオーバーヘッドという二重のボトルネックによって制約される。KV キャッシングは、以前に生成されたトークンの表現を再利用することでデコードを加速するが、大量の GPU メモリを消費し、しばしば主要な容量制約となる。

既存の LLM 推論に関する待ち行列モデルは、通常、計算限界に焦点を当てるか、メモリを静的な制約として扱うに留まっており、推論プロセス中の計算とメモリ増加の動的な相互作用を捉えきれていない。具体的には、リクエストがプロンプト（プリフィル）段階からトークン生成（デコード）段階へと進行するにつれ、そのメモリフットプリントは線形に変化する。リクエストの到着率が、GPU 計算と利用可能な KV キャッシュメモリによって共同決定されるシステムの実効サービス率を超えると、キューは無限に成長し、システムの不安定化、許容できない遅延、およびユーザー体験の低下を招く。これらの動的なメモリ制約を明示的に組み込み、安定性条件を決定し、GPU のプロビジョニングを導くための厳密な理論的枠組みは存在しない。

手法

著者らは、ハードな KV キャッシュメモリ制約（ $M$ ）を受ける離散時間・仕事保存型待ち行列システムとして LLM 推論をモデル化する、新たな待ち行列理論的枠組みを提案する。

1. システムモデル

リクエスト構造: 各リクエスト $i$ は、サイズ $s_i$ のプロンプトと長さ $o_i$ のレスポンスから構成され、結合分布 $F_{in-out}$ からサンプリングされる。
処理フェーズ:
- プロンプトフェーズ: プロンプトは固定サイズチャンク（ $\hat{s}$ ）で処理される。プロンプトの $j$ 番目のチャンクに対するメモリ使用量は線形に増加する（ $j \times \hat{s}$ ）。
- デコードフェーズ: トークンが逐次生成されるにつれ、メモリ使用量はステップごとに 1 トークン分の 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)}$ は処理済みの出力トークンインデックスである。
スケジューリング: この枠組みは、連続バッチ処理と仕事保存ポリシー（例：先着順）を仮定しており、サーバーは容量が許容する限り次の優先度の高いプロンプトを処理する。

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 の部分線形メモリ動力学に適応させたリアプノフ・ドリフト論法を用いて、本論文は 2 つの主要な定理を確立する。

不安定性: 到着率 $\lambda > \mu$ の場合、システムは過負荷となり、リクエスト数は無限に成長する。
安定性: $\lambda < \mu(1 - \delta)$ の場合、ここで $\delta = \frac{\text{ess sup}(s+o)}{M} \ll 1$ は最大単一ジョブを収容するために必要なメモリ余裕を表す。この条件下では、システムは安定する（正再帰的マルコフ連鎖）。

主要な貢献

新規モデリング: 本論文は、計算需要と KV キャッシュによって支配される動的な GPU メモリ制約の両方を明示的に統合する、LLM 推論のための最初の待ち行列モデルを導入する。メモリ認識性を追加し、チャンク化されたプリフィル段階によるスケジューリング設定を洗練させることで、先行モデルを一般化する。
厳密な安定性条件: 著者らは、安定性と不安定性の閉形式条件を導出する。これらの結果は、確率的ワークロード下での LLM サービングシステムの最大持続可能スループットを決定するための原理的な基盤を提供する。
実証的検証: 理論的予測は、実世界の GPU 生産環境（NVIDIA A100）における広範な実験を通じて検証された。単一 GPU およびマルチ GPU（データ並列）構成の両方が対象とされた。

実験結果

著者らは、vLLM 推論エンジンを用いた 8 GPU テストベッド上で Meta-Llama-3-8B モデルを用いて実験を実施した。

精度: 理論的サービス率 $\mu_{theory}$ は、経験的に測定されたレート $\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 サービングシステムにおける正確な安定性分析のために、待ち行列モデルにメモリ動力学を組み込むことが不可欠であることを確認している。