論文の概要: LLM Cache Bandit Revisited: Addressing Query Heterogeneity for Cost-Effective LLM Inference

• arxiv url: http://arxiv.org/abs/2509.15515v1
• Date: Fri, 19 Sep 2025 01:39:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-22 18:18:10.955626
• Title: LLM Cache Bandit Revisited: Addressing Query Heterogeneity for Cost-Effective LLM Inference
• Title（参考訳）: LLMキャッシュ帯域再検討:コスト効果LLM推論のためのクエリ不均一性に対処する
• Authors: Hantao Yang, Hong Xie, Defu Lian, Enhong Chen,
• Abstract要約: 我々は、最適なキャッシュ選択をknapsack問題として扱い、計算オーバーヘッドとキャッシュ更新のバランスをとるために蓄積ベースの戦略を用いる。 我々のアルゴリズムの後悔は$O(sqrtMNT)$boundを達成し、バークレーの$O(MNsqrtT)$と比較して$sqrtMN$の係数を改善することを証明している。 問題に依存したバウンダリも提供しています。
• 参考スコア（独自算出の注目度）: 87.57291812372848
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper revisits the LLM cache bandit problem, with a special focus on addressing the query heterogeneity for cost-effective LLM inference. Previous works often assume uniform query sizes. Heterogeneous query sizes introduce a combinatorial structure for cache selection, making the cache replacement process more computationally and statistically challenging. We treat optimal cache selection as a knapsack problem and employ an accumulation-based strategy to effectively balance computational overhead and cache updates. In theoretical analysis, we prove that the regret of our algorithm achieves an $O(\sqrt{MNT})$ bound, improving the coefficient of $\sqrt{MN}$ compared to the $O(MN\sqrt{T})$ result in Berkeley, where $N$ is the total number of queries and $M$ is the cache size. Additionally, we also provide a problem-dependent bound, which was absent in previous works. The experiment rely on real-world data show that our algorithm reduces the total cost by approximately 12\%.
• Abstract（参考訳）: 本稿では,LLM キャッシュの帯域幅問題を再検討し,コスト効率のよい LLM 推論におけるクエリの不均一性に対処することに着目した。 以前の作業は、しばしば一様クエリサイズを前提とします。 不均一なクエリサイズは、キャッシュ選択のための組合せ構造を導入し、キャッシュ置換プロセスをより計算的かつ統計的に困難にする。 我々は、最適なキャッシュ選択をknapsack問題として扱い、計算オーバーヘッドとキャッシュ更新を効果的にバランスさせるために蓄積ベースの戦略を用いる。 理論的解析において、我々のアルゴリズムの後悔は$O(\sqrt{MNT})$boundを達成し、$O(MN\sqrt{T})$ resultに対して$O(MN\sqrt{MNT})$の係数を改善し、$N$はクエリの総数であり、$M$はキャッシュサイズであることを示す。 さらに、以前の作品では欠落していた問題依存境界も提供します。 この実験は実世界のデータに頼り、我々のアルゴリズムは総コストを約12倍削減することを示した。

関連論文リスト

• Semantic Caching for Low-Cost LLM Serving: From Offline Learning to Online Adaptation [54.61034867177997]
  キャッシング推論応答は、大きな言語モデルに他の前方を通さずに、それらを検索することができる。 従来の正確なキャッシュは、クエリ間のセマンティックな類似性を見落とし、不要な再計算をもたらす。 本稿では,未知のクエリおよびコスト分布下でのセマンティックキャッシュ消去のための,原則的,学習ベースのフレームワークを提案する。
  論文  参考訳（メタデータ） (2025-08-11T06:53:27Z)
• BUZZ: Beehive-structured Sparse KV Cache with Segmented Heavy Hitters for Efficient LLM Inference [2.3587921104010756]
  推論速度を高めつつキャッシュメモリ使用量を最小限に抑える新しいKVキャッシュアルゴリズムであるBUZZを提案する。 BUZZはビーハイブ構造化スパースキャッシュを採用し、スライディングウィンドウを組み込んで最近の情報をキャプチャする。 CNN/Daily Mail, XSUM, Wikitext, 10-QAの4つの実世界のデータセット上でBUZZを評価する。
  論文  参考訳（メタデータ） (2024-10-30T14:53:37Z)
• LLoCO: Learning Long Contexts Offline [63.3458260335454]
  長いコンテキストを処理するための新しいアプローチであるLLoCOを提案する。 LLoCOはコンテキスト圧縮とLoRAによるドメイン内パラメータ効率の微調整を通じて、オフラインでコンテキストを学習する。 提案手法は、4kトークンLLaMA2-7Bモデルの有効コンテキストウインドウを拡張し,最大128kトークンを処理する。
  論文  参考訳（メタデータ） (2024-04-11T17:57:22Z)
• MeanCache: User-Centric Semantic Caching for LLM Web Services [8.350378532274405]
  キャッシングは、繰り返しクエリの推論コストを削減するための自然なソリューションである。 本稿では,LLMベースのサービスのためのユーザ中心セマンティックキャッシュであるMeanCacheを紹介する。 MeanCacheは、セマンティックに類似したクエリを特定して、キャッシュヒットやミスを判定する。
  論文  参考訳（メタデータ） (2024-03-05T06:23:50Z)
• Provably Efficient High-Dimensional Bandit Learning with Batched Feedbacks [93.00280593719513]
  本稿では,オンラインインタラクションのT$ステップをバッチに分割したバッチフィードバックによる高次元マルチアームコンテキストバンドレットについて検討する。 具体的には、各バッチは以前のバッチに依存するポリシーに従ってデータを収集し、その報酬はバッチの最後にのみ明らかにする。 我々のアルゴリズムは,$mathcalO( log T)$ バッチで完全に逐次的に設定されたものに匹敵する後悔の限界を達成している。
  論文  参考訳（メタデータ） (2023-11-22T06:06:54Z)
• JoinGym: An Efficient Query Optimization Environment for Reinforcement Learning [58.71541261221863]
  結合順序選択(JOS)は、クエリの実行コストを最小化するために結合操作を順序付けする問題である。 木質強化学習(RL)のためのクエリ最適化環境JoinGymを提案する。 JoinGymは内部で、事前計算されたデータセットから中間結果の濃度を調べることで、クエリプランのコストをシミュレートする。
  論文  参考訳（メタデータ） (2023-07-21T17:00:06Z)
• MUSTACHE: Multi-Step-Ahead Predictions for Cache Eviction [0.709016563801433]
  MUSTACHEは、既存のポリシーのように修正されるのではなく、観測されたメモリアクセス要求からロジックを学ぶ新しいページキャッシュ置換である。 本稿では,ページ要求予測問題をカテゴリー時系列予測タスクとして定式化する。 提案手法では,学習したページ要求予測器に次の$k$のページメモリ参照を問い合わせ,最適なB'el'adyの置換アルゴリズムをよりよく近似する。
  論文  参考訳（メタデータ） (2022-11-03T23:10:21Z)
• How to Query An Oracle? Efficient Strategies to Label Data [59.89900843097016]
  機械学習におけるデータセットのラベル付けに専門家の託宣を照会する際の基本的な問題について考察する。 本稿では,サンプルをラベル付けするために,ラウンド・バイ・ラウンドでランダム化されたバッチアルゴリズムを提案し,クエリレートが$O(fracNk2)$であることを示す。 さらに,適応型グリージークエリ方式を提案し,三重項クエリを用いたサンプルあたり平均$approx 0.2N$クエリを実現する。
  論文  参考訳（メタデータ） (2021-10-05T20:15:35Z)
• Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with a Faulty Oracle [7.449644976563424]
  本稿では,クラスタリングを不良オラクルで研究するためのエレガントな理論的モデルを提案する。 一般の場合の$k$クラスタに対して、クエリ最適で時間効率のアルゴリズムを得られるかどうかというオープンな疑問として残された。 情報理論の回復が可能であれば,全ての定数$k$に対して,ほぼ最適なクエリ複雑性(最大$O(log2 n)$)を持つ時間効率アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2021-06-18T22:20:12Z)
• Query-Efficient Correlation Clustering [13.085439249887713]
  相関クラスタリングはクラスタリングの最も自然な定式化であることは間違いない。 相関クラスタリングの主な欠点は、入力として$Theta(n2)$ペアの類似性を必要とすることである。 我々は,最大3cdot OPT + O(fracn3Q)$の相違点が期待される解が得られる相関クラスタリングアルゴリズムを考案した。
  論文  参考訳（メタデータ） (2020-02-26T15:18:20Z)

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

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