論文の概要: 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)
• In-context Demonstration Matters: On Prompt Optimization for Pseudo-Supervision Refinement [71.60563181678323]
  大規模言語モデル(LLM)は様々なタスクで大きな成功を収めており、生成品質をさらに向上させるためには微調整が必要である場合もある。 これらの課題に対処する直接的な解決策は、教師なしの下流タスクから高信頼のデータを生成することである。 本稿では,プロンプトと全体的な擬似スーパービジョンを両立させる新しい手法,擬似教師付きデモアライメント・アライメント・アライメント・プロンプト・最適化(PAPO)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-10-04T03:39:28Z)
• Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters [27.656263126925815]
  LLMにおける推論時間計算のスケーリングについて検討する。 どちらの場合も、テスト時間計算のスケーリングに対する異なるアプローチの有効性は、プロンプトの難しさによって大きく異なることがわかった。
  論文  参考訳（メタデータ） (2024-08-06T17:35:05Z)
• 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)
• Switchable Decision: Dynamic Neural Generation Networks [98.61113699324429]
  本稿では,各データインスタンスのリソースを動的に割り当てることで,推論を高速化するスイッチブルな決定を提案する。 提案手法は, 同一の精度を維持しながら, 推論時のコスト低減に有効である。
  論文  参考訳（メタデータ） (2024-05-07T17:44:54Z)
• 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)
• SatLM: Satisfiability-Aided Language Models Using Declarative Prompting [68.40726892904286]
  本研究では,大規模言語モデル (LLM) の推論能力を向上させるために,新しい満足度支援言語モデリング (SatLM) 手法を提案する。 我々はLLMを用いて命令型プログラムではなく宣言型タスク仕様を生成し、既製の自動定理証明器を利用して最終解を導出する。 我々はSATLMを8つの異なるデータセット上で評価し、命令パラダイムにおいてプログラム支援されたLMよりも一貫して優れていることを示す。
  論文  参考訳（メタデータ） (2023-05-16T17:55:51Z)
• RESPECT: Reinforcement Learning based Edge Scheduling on Pipelined Coral Edge TPUs [12.952987240366781]
  本研究は、最適化アルゴリズムの挙動を学習する強化学習(RL)に基づくスケジューリングフレームワークを提案する。 RLは、実行時のオーバーヘッドを短くすることで、ほぼ最適のスケジューリング結果を生成する。 我々のフレームワークは、商用コンパイラ上での実世界のオンチップランタイム推論速度アップを最大$sim2.5times$で実証しています。
  論文  参考訳（メタデータ） (2023-04-10T17:22:12Z)
• 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)
• AsySQN: Faster Vertical Federated Learning Algorithms with Better Computation Resource Utilization [159.75564904944707]
  垂直連合学習(VFL)のための非同期準ニュートン(AsySQN)フレームワークを提案する。 提案アルゴリズムは、逆ヘッセン行列を明示的に計算することなく、近似して降下ステップをスケールする。 本稿では,非同期計算を採用することにより,計算資源の有効利用が期待できることを示す。
  論文  参考訳（メタデータ） (2021-09-26T07:56:10Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

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

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