技術的概要：LLM 推論および AI エージェントのためのスループット最適化スケジューリングアルゴリズム

問題定義

大規模言語モデル（LLM）および AI エージェントへの需要が高まる中、推論システムの効率化を最適化することが極めて重要である。システムレベルの改善に向けた多大なエンジニアリング努力が払われてきた一方で、スケジューリングアルゴリズムを評価するための統合的な数学的モデリングおよび待ち行列理論的枠組みが欠如している。具体的には、本論文は以下の根本的な問いに答える：LLM 推論システムにおける最大スループットレートは何か、また、どのクラスのスケジューリングアルゴリズムがこの限界を達成し得るか？

LLM 推論は、古典的な待ち行列システムと比較して以下のような固有の課題を呈する：

1. 二相処理： リクエストは、入力トークンを処理して KV キャッシュを構築する計算集約的なプリフィルフェーズに続き、自己回帰的なトークン生成を行うメモリ I/O 束縛的なデコードフェーズを経る。
2. バッチング制約： GPU 利用率を最大化するため、リクエストはバッチ処理される。しかし、プリフィルとデコードのトークンを混合すると干渉が生じ、ハードウェアはトークン予算（$b_{max}$）および多くの場合バッチサイズ（$k_{max}$）の制約を課す。
3. AI エージェントワークロード： 現代のアプリケーションは、複雑なエージェントタスクを処理する LLM サーバーのネットワークを含み、これらは有向非巡回グラフ（DAG）トポロジー、フォーク・ジョインパターン、または循環ルーティングに従う可能性がある。

既存のシステムは、異なる優先順位（プリフィル優先対デコード優先）およびバッチング機能（混合対分離）を有する多様な戦略（FasterTransformer、vLLM、Orca、Sarathi-Serve など）を採用している。実務家は現在、システムを選択するためにコストのかかるワークロード固有のベンチマークに依存しており、安定性やスループット最適性に関する理論的保証を欠いている。

手法

著者らは、LLM 推論システムをモデル化するための厳密な待ち行列理論的枠組みを開発した。

1. 確率モデル

• 基本モデル： システムは、2 クラスのバッチサービス待ち行列を表す離散時間マルコフ連鎖（DTMC）としてモデル化される。
  • クラス： リクエストは、プリフィルキューまたはデコードキューのいずれかに存在する。
  • バッチング： サーバーは、トークン予算 $b_{max}$ に従い、両方のキューからトークンのバッチを同時に処理する。
  • 非対称性： 単一リクエストからのプリフィルトークンはバッチ処理可能であるが、デコードトークンは厳密に逐次的（バッチあたりリクエストあたり 1 つ）である。
• 処理時間モデル： 実証的なトレースを活用し、バッチ処理時間 $t_b$ はトークン負荷 $b$ に依存する区分的定数関数で近似される：
  $$t_b = c + a \cdot \lceil b/b_0 \rceil$$
  ここで、$c$ は基本コスト、$a$ は $b_0$ トークンごとのブロックあたりの限界コストである。このモデルは、LLM 推論における線形層計算の支配性を捉える。

2. 解析的枠組み

• 流体極限手法： 著者らは安定性を解析するために流体極限枠組み（Dai 1995, Stolyar 1995）を採用する。特定の条件下で、スケーリングされた確率過程が決定論的な流体モデルに収束することを証明する。
• 安定性の定義： システムが安定（正再帰的）であるとは、時間が無限大に近づくにつれて未処理トークンの総数が発散しないことを意味する。
• スケジューリングクラス： 解析は、可能な限りバッチを容量 $b_{max}$ まで満たすワーク・コンサービングアルゴリズムに焦点を当て、混合バッチングの複雑さを処理するためにK-FCFS条件（有界な追い越しを伴う先着順）を導入する。

3. 拡張

この枠組みは以下に拡張される：

• 並列サーバー： ロードバランシング（ランダムまたは最短キュー結合）を備えたシステム。
• マルチクラスネットワーク： 複数のリクエストクラス（例：異なるエージェントステップ）を処理する単一サーバー。
• ネットワークトポロジー： DAG ルーティングおよびフォーク・ジョイン同期を備えたマルチサーバーネットワーク。
• 循環ルーティング： フィードバックループを備えたネットワークの解析（Rybko–Stolyar 型）。
• バッチサイズ制約： トークン予算（$b_{max}$）および最大バッチサイズ（$k_{max}$）の両方で制約されたシステムの解析。

主要な貢献と結果

1. ワーク・コンサービング・スケジューリングのスループット最適性

本論文は、基本的な設計原則を確立する：ワーク・コンサービング・スケジューリングアルゴリズムは、単一サーバー LLM 推論および DAG またはフォーク・ジョイントポロジーを有するネットワークにおいて、最大スループットを達成する。

• 定理 2： 単一サーバーにおいて、到着負荷 $\lambda(m_p + m_d)$ が最大処理レート $b_{max}/t_{b_{max}}$ より小さい場合、任意のワーク・コンサービング K-FCFS アルゴリズムはシステムを安定化させる。逆に、負荷がこの閾値を超えると、いかなるアルゴリズムのもとでもシステムは不安定になる。
• 含意： これは理論的な上限（$b_{max}/t_{b_{max}}$）を提供し、業界におけるワーク・コンサービング・スケジューラーへの移行を正当化する。

2. 既存システムの評価

理論的枠組みを実世界のアルゴリズムに適用することで、明確な分類が得られる：

• スループット最適（ワーク・コンサービング）：
  • Orca： プリフィル優先を伴う混合バッチング（プリフィル＋デコード）をサポート。
  • Sarathi-Serve： デコード優先を伴うチャンク化プリフィルおよび混合バッチングをサポート。
  • 最新 vLLM（チャンク化プリフィル付き）： ワーク・コンサービング。
• 非最適/不安定（非ワーク・コンサービング）：
  • FasterTransformer： デコードを優先するが混合バッチングを禁止する。プリフィルリクエストが待機していても、デコードリクエストがバッチを埋めるのに不十分な場合、GPU をアイドル状態にする。
  • Vanilla vLLM： プリフィルを優先するが混合バッチングを禁止する。プリフィルのみのバッチを処理している間、デコードリクエストを待機させる。
• 実験的検証： 実世界のトレースは、ワーク・コンサービングアルゴリズム（Sarathi-Serve、Orca）が安定している中程度の負荷下でも、非ワーク・コンサービングアルゴリズム（FasterTransformer、Vanilla vLLM）が不安定化（キューの爆発）することを確認した。

3. AI エージェントワークロードおよびネットワークトポロジー

• DAG およびフォーク・ジョイン： 各サーバーで負荷条件が満たされる限り、DAG またはフォーク・ジョイントポロジーに配置された LLM サーバーのネットワークにおいても、ワーク・コンサービング・スケジューリングがスループット最適であることを証明する。
• 循環ルーティング（Rybko–Stolyar 反例）： 著者らは、循環ルーティングを有するネットワークにおいては、ワーク・コンサービング・スケジューリングだけでは不十分であることを示す。総負荷が容量未満であっても、ワーク・コンサービング方針下での特定の優先順位割り当てが不安定化につながる 2 サーバーネットワークを構築する。これは、循環トポロジーにおいて慎重な優先順位設計または非ワーク・コンサービング方針（例：バックプレッシャー）が必要であることを浮き彫りにする。

4. バッチサイズ制約の影響

トークン予算（$b_{max}$）に加えて最大バッチサイズ制約（$k_{max}$）が課される場合：

• 安定領域は、単純なスカラー閾値ではなく、$(\lambda_{prefill}, \lambda_{decode})$ 平面における2 次元の凸包となる。
• 直感に反する発見： 特定の領域（特に混合バッチを含む安定領域の頂点付近）では、常に $b_{max}$ まで満たす厳密なワーク・コンサービングアルゴリズムは、システムを安定化させるのに失敗する可能性がある。最適な安定性には、プリフィルとデコードの処理レートを均衡させるために、より低いトークン負荷（例：$b_0$）で動作することが必要となる場合がある。これは、厳格なバッチサイズ制約の下では、適応的スケジューリング戦略が必要であることを示唆する。

意義と主張

本論文は、LLM 推論スケジューリングのための最初の厳密な待ち行列理論的基盤を提供すると主張する。その意義は以下の点にある：

1. 設計原則： 実務家にとって「ワーク・コンサービング」を重要な設計原則として特定し、Sarathi-Serve や Orca などのアルゴリズムがスループット最適であるという理論的保証を提供するとともに、FasterTransformer や Vanilla vLLM などの非混合バッチングアプローチに対する警告を与える。
2. コミュニティの架け橋： LLM の固有の二相およびバッチング特性を捉える形式モデルを提供することで、待ち行列理論コミュニティが LLM システムに貢献する際の障壁を低下させる。
3. AI エージェントへの指針： 安定性解析を AI エージェントワークロードに拡張し、DAG トポロジーは堅牢であるが、循環トポロジーには単純なワーク・コンサービング方針よりも高度なスケジューリングが必要であることを明らかにする。
4. 微妙な制約： バッチサイズ制限などの実用的な制約が安定領域を根本的に変え得ることを明らかにし、「バッチを埋めること」が常に最適であるという仮定に疑問を呈する。

著者らは、自らの仕事がスループット最適性の基準を確立した一方で、将来の研究では遅延最適化、注意層などを取り入れたより豊かな処理時間モデル、および複雑な制約やネットワークトポロジーに対する適応的アルゴリズムの設計に取り組む必要があると結論づけている。