論文の概要: Online Scheduling for LLM Inference with KV Cache Constraints
- arxiv url: http://arxiv.org/abs/2502.07115v4
- Date: Tue, 20 May 2025 16:29:52 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-21 14:49:51.774378
- Title: Online Scheduling for LLM Inference with KV Cache Constraints
- Title（参考訳）: KVキャッシュ制約を考慮したLLM推論のためのオンラインスケジューリング
- Authors: Patrick Jaillet, Jiashuo Jiang, Konstantina Mellou, Marco Molinaro, Chara Podimata, Zijie Zhou,
- Abstract要約: 大規模言語モデル(LLM)推論は、レイテンシとリソース利用を最適化するための効率的なスケジューリングを必要とする集約的なプロセスである。
KVキャッシュのメモリを効果的に管理しながら、推論遅延を最小限に抑える、新しい理論的なスケジューリングアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 22.133592174540052
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Large Language Model (LLM) inference, where a trained model generates text one word at a time in response to user prompts, is a computationally intensive process requiring efficient scheduling to optimize latency and resource utilization. A key challenge in LLM inference is the management of the Key-Value (KV) cache, which reduces redundant computations but introduces memory constraints. In this work, we model LLM inference with KV cache constraints theoretically and propose a novel batching and scheduling algorithm that minimizes inference latency while effectively managing the KV cache's memory. More specifically, we make the following contributions. First, to evaluate the performance of online algorithms for scheduling in LLM inference, we introduce a hindsight optimal benchmark, formulated as an integer program that computes the minimum total inference latency under full future information. Second, we prove that no deterministic online algorithm can achieve a constant competitive ratio when the arrival process is arbitrary. Third, motivated by the computational intractability of solving the integer program at scale, we propose a polynomial-time online scheduling algorithm and show that under certain conditions it can achieve a constant competitive ratio. We also demonstrate our algorithm's strong empirical performance by comparing it to the hindsight optimal in a synthetic dataset. Finally, we conduct empirical evaluations on a real-world public LLM inference dataset, simulating the Llama2-70B model on A100 GPUs, and show that our algorithm significantly outperforms the benchmark algorithms. Overall, our results offer a path toward more sustainable and cost-effective LLM deployment.
- Abstract（参考訳）: LLM(Large Language Model)推論(Large Language Model)は、訓練されたモデルがユーザプロンプトに応答して一度に1ワードのテキストを生成するプロセスであり、レイテンシとリソース利用を最適化するために効率的なスケジューリングを必要とする。
LLM推論における重要な課題はキーバリュー(KV)キャッシュの管理である。
本研究では,KVキャッシュのメモリを効果的に管理しつつ,推論遅延を最小限に抑えるバッチ処理とスケジューリングアルゴリズムを提案する。
具体的には、以下のコントリビューションを行います。
まず、LLM推論におけるスケジューリングにおけるオンラインアルゴリズムの性能を評価するために、整数プログラムとして定式化された後向きの最適化ベンチマークを導入し、完全な将来情報の下で最小全推定遅延を計算する。
第二に、決定論的オンラインアルゴリズムが、到着プロセスが任意であれば、一定の競合比を達成できないことを証明する。
第3に、整数プログラムを大規模に解く際の計算難易度から、多項式時間オンラインスケジューリングアルゴリズムを提案し、一定の条件下で一定の競合比が得られることを示す。
また,アルゴリズムの強烈な経験的性能を,合成データセットの後方最適値と比較して示す。
最後に、A100 GPU上でのLlama2-70Bモデルをシミュレーションし、実世界のLLM推論データセット上で経験的評価を行い、我々のアルゴリズムがベンチマークアルゴリズムを大幅に上回っていることを示す。
全体として、我々の結果は、より持続的で費用対効果の高いLCMデプロイメントへの道筋を提供する。
関連論文リスト
- Optimizing LLM Inference: Fluid-Guided Online Scheduling with Memory Constraints [14.341123057506827]
大規模言語モデル(LLM)は、今日のアプリケーションでは必須であるが、推論手順は重要な計算資源を必要とする。
本稿では,多段階オンラインスケジューリング問題としてLLM推論最適化を定式化する。
我々は,アルゴリズム設計をガイドするトラクタブルなベンチマークを提供するために,流体力学近似を開発した。
論文 参考訳（メタデータ） (2025-04-15T16:00:21Z) - Seesaw: High-throughput LLM Inference via Model Re-sharding [8.840996987380484]
本稿ではスループット指向タスクに最適化された推論エンジンであるSeesawを紹介する。
Seesawの背景にある主要なアイデアは、並列化戦略の動的再構成を容易にする技術である動的モデル再シャーディングである。
論文 参考訳（メタデータ） (2025-03-09T04:14:06Z) - MInference 1.0: Accelerating Pre-filling for Long-Context LLMs via Dynamic Sparse Attention [36.49445805074941]
Minference (Milliontokens Inference) は長周期処理の前処理を高速化するスパース計算法である。
我々は,MInferenceが精度を維持しつつ,A100にプリフィルする際の推論遅延を最大10倍に効果的に低減できることを実証した。
論文 参考訳（メタデータ） (2024-07-02T17:59:56Z) - Bypass Back-propagation: Optimization-based Structural Pruning for Large Language Models via Policy Gradient [57.9629676017527]
大規模言語モデルを用いた最適化に基づく構造解析手法を提案する。
我々は,プルーニングモデルの損失を最適化することにより,確率空間におけるプルーニングマスクを直接学習する。
A100 GPUで13Bモデルに対して約35GBのメモリで2.7時間動作させる。
論文 参考訳（メタデータ） (2024-06-15T09:31:03Z) - Latency-aware Unified Dynamic Networks for Efficient Image Recognition [72.8951331472913]
LAUDNetは動的ネットワークの理論的および実用的な効率ギャップを橋渡しするフレームワークである。
3つの主要な動的パラダイム - 適応型計算、動的層スキップ、動的チャネルスキップ - を統合している。
これにより、V100,3090やTX2 GPUのようなプラットフォーム上で、ResNetのようなモデルの遅延を50%以上削減できる。
論文 参考訳（メタデータ） (2023-08-30T10:57:41Z) - Accelerating Exact Combinatorial Optimization via RL-based
Initialization -- A Case Study in Scheduling [1.3053649021965603]
本研究の目的は、最適化問題に対処する機械学習(ML)を用いた革新的なアプローチを開発することである。
1) 粗粒スケジューラとしての解法, 2) 解緩和, 3) ILPによる正確な解法の3つのステップを含む新しい2段階のRL-to-ILPスケジューリングフレームワークを導入する。
提案フレームワークは, 正確なスケジューリング手法と比較して, 最大128ドルの高速化を実現しつつ, 同一のスケジューリング性能を示す。
論文 参考訳（メタデータ） (2023-08-19T15:52:43Z) - Maximize to Explore: One Objective Function Fusing Estimation, Planning,
and Exploration [87.53543137162488]
我々はtextttMEX というオンライン強化学習(オンラインRL)フレームワークを提案する。
textttMEXは、自動的に探索エクスプロイトのバランスをとりながら、見積もりと計画コンポーネントを統合する。
様々な MuJoCo 環境では,ベースラインを安定的なマージンで上回り,十分な報酬を得られる。
論文 参考訳（メタデータ） (2023-05-29T17:25:26Z) - Response Length Perception and Sequence Scheduling: An LLM-Empowered LLM
Inference Pipeline [22.08897444328099]
大規模言語モデル(LLM)はAIの分野に革命をもたらし、様々なタスクで前例のない能力を示している。
本稿では,LLMのパワーを利用する効率的なLLM推論パイプラインを提案する。
論文 参考訳（メタデータ） (2023-05-22T15:36:06Z) - Making Linear MDPs Practical via Contrastive Representation Learning [101.75885788118131]
マルコフ決定過程(MDP)における次元性の呪いに、低ランク表現を利用することで対処することが一般的である。
本稿では,効率的な表現学習を可能にしつつ,正規化を自動的に保証する線形MDPの代替的定義について考察する。
いくつかのベンチマークにおいて、既存の最先端モデルベースおよびモデルフリーアルゴリズムよりも優れた性能を示す。
論文 参考訳（メタデータ） (2022-07-14T18:18:02Z) - Accelerating Deep Learning Classification with Error-controlled
Approximate-key Caching [72.50506500576746]
我々は、近似キーキャッシングと名付けた新しいキャッシングパラダイムを提案する。
近似キャッシュはDL推論の負荷を軽減し、システムのスループットを向上するが、近似誤差を導入する。
我々は古典的なLRUと理想的なキャッシュのキャッシュシステム性能を解析的にモデル化し、期待される性能のトレース駆動評価を行い、提案手法の利点を最先端の類似キャッシュと比較した。
論文 参考訳（メタデータ） (2021-12-13T13:49:11Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。