論文の概要: LLM Serving Optimization with Variable Prefill and Decode Lengths

• arxiv url: http://arxiv.org/abs/2508.06133v1
• Date: Fri, 08 Aug 2025 08:54:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-11 20:39:06.155534
• Title: LLM Serving Optimization with Variable Prefill and Decode Lengths
• Title（参考訳）: 可変プリフィルとデコード長を用いたLLMサービング最適化
• Authors: Meixuan Wang, Yinyu Ye, Zijie Zhou,
• Abstract要約: 本研究では,各要求が不均一なプレフィルとデコード長を持つLLM要求(Large Language Model)を提供する問題について検討する。 この問題は、配置制約の相互運用、優先関係、メモリ使用量の線形増加などによりNPハードであることが示される。 本稿では,時間とともに効率よくバッチを生成する新しい選択基準に基づく新しいアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 2.666596421430287
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of serving LLM (Large Language Model) requests where each request has heterogeneous prefill and decode lengths. In LLM serving, the prefill length corresponds to the input prompt length, which determines the initial memory usage in the KV cache. The decode length refers to the number of output tokens generated sequentially, with each additional token increasing the KV cache memory usage by one unit. Given a set of n requests, our goal is to schedule and process them to minimize the total completion time. We show that this problem is NP-hard due to the interplay of batching, placement constraints, precedence relationships, and linearly increasing memory usage. We then analyze commonly used scheduling strategies in practice, such as First-Come-First-Serve (FCFS) and Shortest-First (SF), and prove that their competitive ratios scale up sublinearly with the memory limit-a significant drawback in real-world settings where memory demand is large. To address this, we propose a novel algorithm based on a new selection metric that efficiently forms batches over time. We prove that this algorithm achieves a constant competitive ratio. Finally, we develop and evaluate a few algorithm variants inspired by this approach, including dynamic programming variants, local search methods, and an LP-based scheduler, demonstrating through comprehensive simulations that they outperform standard baselines while maintaining computational efficiency.
• Abstract（参考訳）: 各要求が不均一なプレフィルとデコード長を持つLLM要求(Large Language Model)を提供する問題について検討する。 LLMサービスでは、プリフィル長は入力プロンプト長に対応し、KVキャッシュにおける初期メモリ使用量を決定する。 デコード長は連続的に生成される出力トークンの数を指し、各追加トークンはKVキャッシュメモリ使用量を1単位増やす。 n リクエストのセットが与えられた場合、我々のゴールは、全完了時間を最小化するためにスケジュールと処理を行うことです。 この問題は,バッチ処理や配置制約,優先関係,メモリ使用量の増加などによるNPハードな問題であることが示される。 次に,FCFS (First-Come-First-Serve) やSF (Shortest-First) などの一般的なスケジューリング手法を解析し,メモリ需要が大きい実世界の環境において,その競合比がメモリ限界に比例して増加することを証明した。 そこで本研究では,時間とともに効率よくバッチを生成する新しい選択基準に基づく新しいアルゴリズムを提案する。 我々は,このアルゴリズムが一定の競合比を達成することを証明した。 最後に、動的プログラミングの変種、局所探索法、LPベースのスケジューラなど、このアプローチにインスパイアされたいくつかのアルゴリズム変種を開発し、評価し、計算効率を保ちながら標準ベースラインより優れていることを示す。

関連論文リスト

• Optimizing LLM Inference: Fluid-Guided Online Scheduling with Memory Constraints [14.341123057506827]
  大規模言語モデル(LLM)は、今日のアプリケーションでは必須であるが、推論手順は重要な計算資源を必要とする。 本稿では,多段階オンラインスケジューリング問題としてLLM推論最適化を定式化する。 我々は,アルゴリズム設計をガイドするトラクタブルなベンチマークを提供するために,流体力学近似を開発した。
  論文  参考訳（メタデータ） (2025-04-15T16:00:21Z)
• LServe: Efficient Long-sequence LLM Serving with Unified Sparse Attention [26.54297116028556]
  大規模言語モデル(LLM)は、長いシーケンスや複雑な推論タスクの処理において顕著な可能性を示している。 LServeは,ハイブリッドスパースアテンションにより長周期LLMサービスを高速化する,効率的なシステムである。 LServeはLLMプリフィルを最大2.9倍加速し、vLLMで1.3-2.1倍デコードする。
  論文  参考訳（メタデータ） (2025-02-20T18:59:52Z)
• Squeezed Attention: Accelerating Long Context Length LLM Inference [61.787865959140994]
  本稿では,入力コンテキストの大部分を固定したアプリケーションを高速化するために,Squeezed Attentionを提案する。 推論中、ユーザ入力からのクエリトークンとセントロイドを比較し、固定されたコンテキストからどのキーが意味論的に関連しているかを予測する。 また,線形から対数的への注意の複雑さを,固定した文脈長に対して低減できる階層型アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-14T18:54:19Z)
• Don't Stop Me Now: Embedding Based Scheduling for LLMs [22.099820814682513]
  SRPT(Shortest Remaining Process Time)のようなサイズベースのスケジューリングアルゴリズムは、平均的な要求完了時間を削減することを目的としている。 LLMシステムにおけるメモリオーバーヘッドを考慮した予測型SRPT変種を提案する。
  論文  参考訳（メタデータ） (2024-10-01T19:51:07Z)
• Training-Free Exponential Context Extension via Cascading KV Cache [49.608367376911694]
  カスケードサブキャッシュバッファを利用して,最も関連性の高いトークンを選択的に保持する機構を導入する。 本手法は,1Mトークンのフラッシュアテンションと比較して,プリフィルステージ遅延を6.8倍削減する。
  論文  参考訳（メタデータ） (2024-06-24T03:59:17Z)
• Hierarchical Context Merging: Better Long Context Understanding for Pre-trained LLMs [61.40047491337793]
  本稿では,大規模言語モデルの制約を克服する新しいトレーニングフリースキームである階層型cOntext MERging(HOMER)を提案する。 HomeRは、長いインプットを管理可能なチャンクに分割する、分別/対数アルゴリズムを使用する。 トークン削減技術がマージ毎に先行し、メモリ使用効率が保証される。
  論文  参考訳（メタデータ） (2024-04-16T06:34:08Z)

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

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