論文の概要: Asymptotic Optimality of $cμ$-Rule for LLM Inference Scheduling under Memory Constraint

• arxiv url: http://arxiv.org/abs/2611.04807v1
• Date: Tue, 03 Nov 2026 12:41:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-09 13:20:13.501193
• Title: Asymptotic Optimality of $cμ$-Rule for LLM Inference Scheduling under Memory Constraint
• Title（参考訳）: メモリ制約下でのLLM推論スケジューリングにおける$cμ$-Ruleの漸近最適性
• Abstract要約: エージェントおよび推論ワークロードにおける長い入力プロンプトと生成シーケンスは、重要なキー値キャッシュの使用につながる。 我々は,効率的なサービスレートのキャプチャ,メモリアクセス,メモリ容量を備えた単一サーバキューにシステムを還元する流体モデルを開発した。 このルールは流体モデルにおける累積保持コストを最小化し、有限のワークロードに対しては、完了時間を最小化し、フルラン出力トーケンスループットを最大化する。
• 参考スコア（独自算出の注目度）: 11.495253774507118
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Large language model (LLM) inference, the process by which a pre-trained model receives an input prompt and generates output tokens sequentially, has become increasingly important with the widespread deployment of LLM-based applications. As inference workloads continue to scale, GPU memory has emerged as a critical bottleneck: the long input prompts and generation sequences common in agentic and reasoning workloads lead to substantial key-value (KV) cache usage. In this paper, we study the resulting online scheduling problem from a queueing perspective. Requests arrive stochastically with heterogeneous prompt and output lengths, undergo prefill and autoregressive decode, and compete for a finite KV-cache capacity. Unlike classical queueing models, the duration of a processing step depends on both prefill computation and KV-cache I/O, so service capacity is jointly determined by computation, memory access, and memory occupancy. We develop a fluid model that reduces the system to a multiclass single-server queue with effective service rates capturing computation, memory access, and memory capacity. This fluid analysis yields a $cμ$ priority rule, where the effective service rate $μ$ is jointly determined by computational speed, memory bandwidth, and memory capacity. We prove that this rule minimizes cumulative holding cost in the fluid model and, for a finite workload, also minimizes completion time and maximizes full-run output-token throughput. We then construct a feasible scheduling policy for the original finite system and prove that its scaled dynamics converge to the optimal fluid policy. Finally, experiments on a real LLM serving engine using an NVIDIA H800 show that practical implementations of the proposed priority rule substantially reduce average latency while maintaining high throughput relative to existing scheduling policies.
• Abstract（参考訳）: 事前学習されたモデルが入力プロンプトを受信し、出力トークンを逐次生成するプロセスである大規模言語モデル(LLM)は、LLMベースのアプリケーションの普及に伴い、ますます重要になっている。 エージェントや推論ワークロードに共通する長いインプットプロンプトと生成シーケンスは、キーバリュー(KV)キャッシュの使用に相当します。 本稿では,待ち行列の観点からオンラインスケジューリング問題について考察する。 要求は不均一なプロンプトと出力長で確率的に到達し、プリフィルと自己回帰デコードを実行し、有限のKVキャッシュ能力で競合する。 従来の待ち行列モデルとは異なり、処理ステップの持続時間はプリフィル計算とKV-cache I/Oの両方に依存するため、サービス容量は計算、メモリアクセス、メモリ占有によって共同で決定される。 本研究では,計算量,メモリアクセス量,メモリ容量を効果的に捉えたマルチクラス単一サーバキューにシステムを還元する流体モデルを構築した。 この流体分析により、$cμ$の優先度ルールが得られ、有効なサービスレート$μ$は計算速度、メモリ帯域幅、メモリ容量によって共同で決定される。 このルールは流体モデルにおける累積保持コストを最小化し、有限のワークロードに対しては、完了時間を最小化し、フルラン出力トーケンスループットを最大化する。 次に、元の有限系に対して実行可能なスケジューリングポリシを構築し、そのスケールされたダイナミクスが最適流体ポリシーに収束することを証明する。 最後に,NVIDIA H800 を用いた実 LLM サービスエンジンの実験により,提案した優先度規則の実用的な実装により,既存のスケジューリングポリシと比較して高いスループットを維持しつつ,平均遅延を大幅に低減することを示した。

関連論文リスト

• LLM Inference in a Flash! [66.43896490006965]
  大規模言語モデル(LLM)は、さまざまな自然言語処理タスクで印象的な機能を示している。 我々は、高価な浮動小数点演算をなくすために、エンドツーエンドの整数のみの量子化手法を提案する。
  論文  参考訳（メタデータ） (2026-09-14T18:04:30Z)
• LLM Serving Optimization with Variable Prefill and Decode Lengths [6.937936394246354]
  本研究では,各要求が不均一なプレフィルとデコード長を持つLLM要求(Large Language Model)を提供する問題について検討する。 この問題は、配置制約の相互運用、優先関係、メモリ使用量の線形増加などによりNPハードであることが示される。 本稿では,時間とともに効率よくバッチを生成する新しい選択基準に基づく新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-08-08T08:54:21Z)
• Optimizing LLM Inference: Fluid-Guided Online Scheduling with Memory Constraints [14.341123057506827]
  大規模言語モデル(LLM)は、今日のアプリケーションでは必須であるが、推論手順は重要な計算資源を必要とする。 本稿では,多段階オンラインスケジューリング問題としてLLM推論最適化を定式化する。 我々は,アルゴリズム設計をガイドするトラクタブルなベンチマークを提供するために,流体力学近似を開発した。
  論文  参考訳（メタデータ） (2025-04-15T16:00:21Z)
• Online Scheduling for LLM Inference with KV Cache Constraints [22.133592174540052]
  大規模言語モデル(LLM)推論は、レイテンシとリソース利用を最適化するための効率的なスケジューリングを必要とする集約的なプロセスである。 KVキャッシュのメモリを効果的に管理しながら、推論遅延を最小限に抑える、新しい理論的なスケジューリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-02-10T23:11:44Z)
• ThinK: Thinner Key Cache by Query-Driven Pruning [63.13363917871414]
  大規模言語モデル(LLM)は自然言語処理の分野に革命をもたらし、様々なアプリケーションで前例のない性能を達成した。 本稿では,KVキャッシュのメモリ消費の非効率性に対処する長文シナリオに焦点を当てた。 我々は,最小のチャネルを選択的に切断しながら,注目重量損失を最小限に抑える新しいクエリ依存型KVキャッシュプルーニング手法であるThinKを提案する。
  論文  参考訳（メタデータ） (2024-07-30T17:59:08Z)
• Training-Free Exponential Context Extension via Cascading KV Cache [49.608367376911694]
  カスケードサブキャッシュバッファを利用して,最も関連性の高いトークンを選択的に保持する機構を導入する。 本手法は,1Mトークンのフラッシュアテンションと比較して,プリフィルステージ遅延を6.8倍削減する。
  論文  参考訳（メタデータ） (2024-06-24T03:59:17Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。