論文の概要: Compression Barriers for Autoregressive Transformers

• arxiv url: http://arxiv.org/abs/2502.15955v1
• Date: Fri, 21 Feb 2025 21:37:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-25 15:56:17.362351
• Title: Compression Barriers for Autoregressive Transformers
• Title（参考訳）: 自己回帰変換器の圧縮バリア
• Authors: Themistoklis Haris, Krzysztof Onak,
• Abstract要約: 自己回帰変換器の鍵となる制限は、以前のキー値の埋め込みをキャッシュするために必要な大きなメモリである。 任意のアルゴリズムが$Omega(dcdot ed)$空間を必要としていることを示し、ザンディー、ハン、ミロクニ、カルバシによって提案された SubGen の被覆数に対する厳密な境界を用いて証明する。
• 参考スコア（独自算出の注目度）: 0.8331054243801623
• License:
• Abstract: A key limitation of autoregressive Transformers is the large memory needed at inference-time to cache all previous key-value (KV) embeddings. Prior works address this by compressing the KV cache, but often assume specific structural properties of the embeddings. This raises the following natural question: Can truly sublinear space utilization be achieved without such assumptions? In this work, we answer this question in the negative. Any algorithm for attention-based token generation must use $\Theta(nd)$ space, where $n$ is the number of tokens generated so far and $d = \Omega(\log n)$ is the dimension of the KV embeddings. Our proof involves a reduction from a classic communication complexity problem and uses a randomized construction that leverages properties of projections in the spirit of the Johnson-Linderstrauss lemma. For the low-dimensional regime $d = o(\log n)$, we show that any algorithm requires $\Omega(d\cdot e^d)$ space and prove, using tight bounds on covering numbers, that SubGen, proposed by Zandieh, Han, Mirrokni and Karbasi, matches this bound. Further, we investigate how sparsity assumptions enable token generation in truly sublinear space, presenting impossibility results and proposing a new KV cache compression algorithm for sliding window attention when the value cache outside the window is unmasked. Finally, we analyze token generation's time complexity, using an indistinguishability argument to prove that no non-adaptive algorithm can compute attention online in sublinear time for all tokens.
• Abstract（参考訳）: 自己回帰変換器の鍵となる制限は、すべてのキー値(KV)埋め込みをキャッシュするために推論時に必要とされる大きなメモリである。 以前の作業では、KVキャッシュを圧縮することでこの問題に対処するが、しばしば埋め込みの特定の構造特性を仮定する。 真の部分線型空間利用はそのような仮定なしで達成できるのか? この研究では、この疑問に否定的に答える。 注意に基づくトークン生成のためのアルゴリズムは、$\Theta(nd)$ spaceを使用しなければならず、$n$はこれまでに生成したトークンの数であり、$d = \Omega(\log n)$はKV埋め込みの次元である。 我々の証明は、古典的な通信複雑性問題から還元され、ジョンソン・リンダーシュトラウス補題の精神における射影の性質を利用するランダム化構造を用いる。 低次元のレジーム $d = o(\log n)$ に対して、任意のアルゴリズムは$\Omega(d\cdot e^d)$空間を必要とし、被覆数上の厳密な境界を用いて証明する。 さらに,空間内におけるスペーサ性仮定により,真のサブ線形空間におけるトークン生成が実現し,不合理性を示すとともに,ウィンドウ外部の値キャッシュがマスキングされていない場合に,窓の注意をスライドさせる新しいKVキャッシュ圧縮アルゴリズムを提案する。 最後に、非適応アルゴリズムが全てのトークンに対してサブ線形時間でオンラインの注意を計算できないことを示すために、区別不可能な引数を用いてトークン生成の時間複雑性を分析する。

関連論文リスト

• Efficient Long-Decoding Inference with Reasoning-Aware Attention Sparsity [14.409253716114213]
  推論タスクを解くには、時間とメモリ消費の$O(N)を発生させる(思考の)長いデコードチェーンを必要とすることが多い。 我々はRaaSという新しいアルゴリズムを提案し、マイルストーントークンを識別し、保持するが、それはもはや必要なくなるまでである。 このパターンに基づいて,$O(L)$時間と$O(L)$メモリの複雑さで精度の高いRaaSというアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-02-16T14:28:52Z)
• ZETA: Leveraging Z-order Curves for Efficient Top-k Attention [22.90397380324185]
  本稿では,全シーケンスに対する過去のトークンの並列クエリを可能にするZETAを提案する。 ZETA は合成textscMulti-Query Associative Recall タスクにおける標準注意性能と一致する。
  論文  参考訳（メタデータ） (2025-01-24T15:33:05Z)
• A Training-free Sub-quadratic Cost Transformer Model Serving Framework With Hierarchically Pruned Attention [43.211427581302715]
  大規模言語モデルにおける文脈長を増大させるため,HiP(Hierarchically Pruned Attention)を提案する。 HiPは注意機構の時間的複雑さを$O(T log T)$に減らし、空間的複雑さを$O(T)$に減らし、$T$はシーケンス長である。 HiPは, 劣化を最小限に抑えつつ, プリフィルとデコードの両方のレイテンシとメモリ使用率を著しく低減することを示す。
  論文  参考訳（メタデータ） (2024-06-14T08:32:45Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• Get More with LESS: Synthesizing Recurrence with KV Cache Compression for Efficient LLM Inference [78.65321721142624]
  我々はキー値(KV)キャッシュによって課されるメモリボトルネックに焦点を当てる。 既存のKVキャッシュ手法は、比較的重要でないKVペアの大きなスワストを刈り取ったり、取り除いたりすることでこの問題に対処する。 本稿では,固定サイズキャッシュと退避型キャッシュを簡易に統合したLESSを提案する。
  論文  参考訳（メタデータ） (2024-02-14T18:54:56Z)
• One Pass Streaming Algorithm for Super Long Token Attention Approximation in Sublinear Space [11.735802740426294]
  注意計算は、$O(n2)$の時間複雑性と$O(n2)$の空間複雑性を同時に行う。 ストリーミング方式で1パスのデータのみを読み取る新しいアルゴリズムを導入する。 特に,本アルゴリズムは,超長期トークンを用いたメモリ効率の優れた性能を示す。
  論文  参考訳（メタデータ） (2023-11-24T18:35:00Z)
• H$_2$O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models [110.06476624089679]
  メモリフットプリントを大幅に削減する新しいKVキャッシュの実装手法を提案する。 我々のアプローチは、トークンのごく一部が、注意点の計算において、ほとんどの価値に寄与する、という観察に基づいている。 我々は,最近のトークンとH$のバランスを動的に保持するKVキャッシュ消去ポリシーであるヘビーヒッター(H$O)を提案する。
  論文  参考訳（メタデータ） (2023-06-24T20:11:14Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。 最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
  論文  参考訳（メタデータ） (2022-06-17T09:24:41Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)

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

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