技術要約: CASCADE

問題提起

大規模言語モデル（LLM）のサービングプラットフォームは、現在、サービスレベル目標（SLO）と、流入するリクエストの不均一性との間の根本的なミスマッチに直面している。SLO（具体的には、Time-to-First-Token [TTFT] および Time-Per-Output-Token [TPOT]）はサービスレベルで定義されるが、個々のリクエストの実行コストは、入力長、生成長、および再利用可能なKey-Value（KV）キャッシュ状態の可用性の違いにより、数桁のオーダーで変動する。

vLLMなどの既存のサービングシステムは、通常、先着順（FCFS）スケジューリングや単純なサイズベースのヒューリスティック（例：最短ジョブ優先 [Shortest Job First]）を採用している。これらのアプローチは、個々のリクエストの「レイテンシ・バジェット（許容時間）」、すなわち、リクエストのSLOデッドラインと予測される実行時間の差を考慮できていない。その結果、以下の問題が発生する：

1. ヘッドオブライン（HOL）ブロッキング: 長文コンテキストのリクエストが短文かつ緊急のリクエストをブロックし、後者のSLO違反を引き起こす。
2. 非効率的なKV管理: システムは、計算時間を節約するために、深いメモリ階層（例：NVMe）からKV状態を呼び出すことが多い。しかし、リクエストするタスクの特定のレイテンシ・バジェットを考慮しない場合、これらの転送がリクエストの残りのSLOヘッドルームを超える遅延を導入し、キャッシュヒットをSLO違反へと変えてしまう。
3. 不公平性: 短いジョブを優先するポリシー（SJF）は、長文コンテキストのワークロード（例：コーディングエージェント、推論タスク）を系統的に飢餓状態（スターベーション）に陥れる。一方で、FCFSは、十分な予算を持つリクエストと、極めて緊急なリクエストを区別できない。

既存のスケジューラは、リクエストの順序付けとKVキャッシュ管理を独立した問題として扱っており、両者が同じリソース、すなわち「リクエストごとのレイテンシ・バジェット」を消費しているという事実を見落としている。

メソドロジー: CASCADEシステム

CASCADEは、統一されたリクエストごとのレイテンシ・バジェットを用いて、リクエストのスケジューリングとマルチティアKVキャッシュ管理を共同で調整するように設計されたLLMサービングシステムである。

1. レイテンシ・バジェットの定義と推定

CASCADEは、リクエスト $r$ のレイテンシ・バジェット ($B_r$) を次のように定義する：
$$B_r = S_{TTFT}^{c(r)} - L_r$$
ここで、$S_{TTFT}^{c(r)}$ はクラスレベルのSLOターゲットであり、$L_r$ は推定される残りのサービス時間である。

• 推定: システムは、入力長、予測される出力長、メモリ階層（HBM、DRAM、NVMe）全体にわたる利用可能なプレフィックスKV状態、および現在のシステム負荷に基づき、プリフィル（prefill）レイテンシをモデル化するTTFTレイテンシ推定器を使用する。
• 保守性: 信頼性を確保するため、推定器は実際の負荷および最大容量下での予測レイテンシを平均化し、推定誤差や競合を考慮するために経験的なガードバンド係数（$\gamma$）によってスケーリングを行う。

2. デュアルティア・スケジューリング・アーキテクチャ

CASCADEは、算出されたバジェットに基づいた2段階のキューイングメカニズムを利用する：

• ティア1（正のバジェット）: $B_r > 0$ であるリクエストは、優先度付きキューに受理される。これらは**最小残りバジェット優先（Least-Remaining-Budget-First）**の順序でスケジューリングされる。これにより、入力サイズに関わらず、デッドラインが差し迫っている（残りバジェットが少ない）リクエストが、ヘッドルームが十分にあるリクエストよりも優先される。
• ティア2（負のバジェット）: $B_r \le 0$ であるリクエストは、二次的なキューに格下げされる。これらは破棄されるのではなく、クラスターのアイドル期間中に機会主義的に実行される。負荷の減少に伴い、リクエストがティア1に昇格できるように、各バッチの一定割合がティア2のために確保される。

3. バジェットを考慮したKVキャッシュ管理

同じレイテンシ・バジェットが、メモリ階層（GPU HBM、CPU DRAM、NVMe）にわたるメモリ決定を制御する：

• 実行可能な復元: プレフィックスKV状態が深い階層で見つかった場合、CASCADEはそれを復元するために必要な転送時間を計算する。転送がリクエストの残りのバジェット内に収まる場合にのみ、復元が開始される。
• 再計算へのフォールバック: 転送遅延がSLOを違反する場合、システムは深い階層からのフェッチを回避し、プレフィックスをGPU上で再計算することで、SLO違反を防ぐ。
• プリエンプション（中断）: HBMメモリの圧迫下において、CASCADEは残りのバジェットが最大であるアクティブなリクエストをプリエンプトする。これらのリクエストには大きなヘッドルームがあるため、再実行のオーバーヘッドがSLO違反を引き起こす可能性は低い。

4. 実装

CASCADEは、vLLMサービングエンジンを拡張するものとして実装されている。これは、マルチティアKVブロックの配置と移動のためにLMCacheと統合されている。システムは、メタデータ（SLO、推定レイテンシ、到着時刻）を既存のリクエストオブジェクトにスレッドし、CPU上でバジェット計算を行うことで、GPU実行とオーバーラップさせ、最小限のオーバーヘッドで動作する。

主な貢献

1. 共通のリソースとしてのレイテンシ・バジェットの特定: 本論文は、リクエストのスケジューリングとKVキャッシュの移動が、同じリソースである「リクエストごとのレイテンシ・バジェット」を奪い合っていることを特定した。サービスデッドライン、リクエストサイズ、およびキャッシュ状態だけでは、リクエストがどの程度のオーバーヘッドを許容できるかを判断するには不十分であることを示している。
2. 共同調整メカニズム: CASCADEは、リクエストの順序付けと、メモリ階層全体におけるKV復元、プリフェッチ、配置、および再計算を調整するために、個別のレイテンシ・バジェットを維持・更新するLLMサービングシステムを提示する。
3. 公平で高グッドスループなスケジューリング: 提案されたバジェットベースのスケジューラは、長文コンテキストのリクエストを系統的に飢餓状態に陥れることなくHOLブロッキングを軽減し、多様なリクエストクラスにわたる公平性を維持する。
4. 実証的検証: NVIDIA GB200 NVL72ハードウェアプロファイルを用い、3つの大規模モデル（Qwen-2.5-72B, Llama-3-70B, Llama-3-405B）にわたるプロダクション・トレースを用いて評価を行った。

結果

ChatBot、Tool&Agent、Coder、Reasoningのワークロードを含むプロダクション・トレースを用いた評価により、以下が示された：

• グッドスループの向上: CASCADEは、デフォルトのvLLM FCFSスケジューラと比較して、SLOを満たしたグッドスループを最大2.4倍向上させる。
• SLO違反の削減: FCFSに対してSLO違反を**40%**削減する。
• 公平性: CASCADEは、異なるリクエストサイズクラス間で高いJainの公平性指数（1.0に近い値）を維持する。一方、最短ジョブ優先（SJF）は、重いワークロード下で長文コンテキストのリクエストに深刻な飢餓を引き起こし、公平性を約0.6まで低下させる。
• 堅牢性: 高負荷およびクラスター容量の減少下においても、CASCADEは高いグッドスループと低い違反率を維持するが、ベースラインは深刻なHOLブロッキングとキューの蓄積に苦しむ。

意義と主張

本論文は、現在のシステムにおけるSLO違反の主な原因は、計算能力（compute budget）の不足ではなく、HOLブロッキングや調整されていないKVキャッシュ転送による、この計算能力の浪費であると主張している。レイテンシ・バジェットを明示的な実行時量として扱うことで、CASCADEは、避けられないオーバーヘッド（キューイング、データ移動）を、それらを吸収できるリクエストへと向け、緊急のリクエストを保護する。

著者らは、このアプローチにより、追加のハードウェアやモデルの重みの変更を必要とすることなく、多様なアプリケーションタイプ（短いチャットインタラクションから長い推論タスクまで）にわたって、厳密なレイテンシSLOを遵守しつつ、アクセラレータの利用率とグッドスループを最大化できると断言している。本システムは、スケジューリングとメモリ管理の間の溝を埋め、それらを各リクエストの具体的な緊急性に駆動された、統一された最適化問題として扱うものである。