論文の概要: Attention under Bounded Key-Query Similarity: Space Complexity and Transformer Anisotropy

• arxiv url: http://arxiv.org/abs/2610.35020v1
• Date: Mon, 26 Oct 2026 08:31:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-27 22:27:13.796979
• Title: Attention under Bounded Key-Query Similarity: Space Complexity and Transformer Anisotropy
• Title（参考訳）: 境界キークエリ類似性に基づく注意:空間複雑度と変圧器異方性
• Abstract要約: KV-cache圧縮は、自己回帰生成のメモリ要求を減らすことを目的としている。 ほぼ空間最適アルゴリズムと対応する空間下界を与える。 このアルゴリズムは,パラメータの典型的な範囲に対してほぼ最適であることを示す。
• 参考スコア（独自算出の注目度）: 23.994623370320323
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A growing body of work on KV-cache compression aims to reduce the memory requirements of autoregressive generation. These methods compress the stored context while approximately preserving attention computation, enabling generation with reduced memory consumption. Almost tight theoretical results on the worst case space complexity of attention have recently been obtained, but they are achieved by instances where queries can be perfectly aligned with keys. This directly contradicts the observed anisotropy of the key/query geometry in real transformers. In particular, it has been shown empirically that key/query cosine similarities are small even for most correlated pairs, i.e., near-perfect alignment of queries with keys does not happen in practice. In this paper, we study the space complexity of attention approximation under the assumption that key/query cosine similarities belong to a small interval around zero, i.e., a query cannot align too much with any key. We give a nearly space optimal algorithm and a corresponding space lower bound. Surprisingly, the distribution of key/query cosine similarities in our lower bound exhibits the anisotropy property empirically established and studied in the literature. Additionally, we show that the simple uniform sampling algorithm is nearly optimal for a typical range of parameters, supporting its surprising effectiveness on real datasets.
• Abstract（参考訳）: KV-cache圧縮の取り組みは、自己回帰生成のメモリ要求を減らすことを目的としている。 これらの方法は、注意計算をほぼ保存しながら記憶されたコンテキストを圧縮し、メモリ消費を削減した生成を可能にする。 最悪の場合の空間複雑性に関するほぼ理論的な結果が最近得られたが、クエリがキーと完全に整合できるインスタンスによって達成されている。 これは、実変圧器におけるキー/クエリ幾何学の観測された異方性と直接矛盾する。 特に、キー/クエリのコサイン類似性は、ほとんどの相関するペアであっても小さいことが実証的に示されている。 本稿では,キー/クエリのコサイン類似性が0付近の小さな区間に属するという仮定の下で,注意近似の空間的複雑さについて検討する。 ほぼ空間最適アルゴリズムと対応する空間下界を与える。 驚くべきことに,我々の下界におけるキー/クリーコサイン類似性の分布は,実証的に確立され,文献で研究されている異方性特性を示す。 さらに、本アルゴリズムは、パラメータの典型的な範囲に対してほぼ最適であり、実際のデータセット上での驚くべき効果を裏付けるものであることを示す。

関連論文リスト

• Bridging the Gap Between Homogeneous and Heterogeneous Asynchronous Optimization Is Surprisingly Difficult [67.12978375116599]
  ランダム化アルゴリズムの1階と2階の類似性仮定において、改善は証明不可能であることを示す。 我々は、労働者の計算時間に依存した新しい時間複雑性を、同質な設定で最もよく知られた結果に導出する。
  論文  参考訳（メタデータ） (2026-09-15T17:24:09Z)
• Decomposing Query-Key Feature Interactions Using Contrastive Covariances [75.38737409771085]
  クエリとキー間の双方向のジョイント埋め込み空間であるクエリキー空間について検討する。 キーとクエリの機能がこれらの低ランクのサブスペースに整列して、高い注目スコアが生成されるときです。
  論文  参考訳（メタデータ） (2026-02-04T16:50:02Z)
• Homogeneous Keys, Heterogeneous Values: Exploiting Local KV Cache Asymmetry for Long-Context LLMs [28.554617623874176]
  我々は、KVキャッシュにおいて、基本的かつ以前見過ごされた非対称性を示す。 キー値の非対称性は、既存の圧縮法に限界があることを示している。 均質性に基づく鍵マージと数学的に証明されたロスレス値圧縮を併用したトレーニングフリー圧縮フレームワーク(AsymKV)を提案する。
  論文  参考訳（メタデータ） (2025-06-04T16:10:44Z)
• Statistical Mechanics of Semantic Compression [0.0]
  我々は,認知神経科学と機械学習からインスピレーションを得て,連続ユークリッドベクトル空間としてのセマンティック空間をモデル化する。 我々は、最小長の意味保存メッセージを決定する最適化問題をスピングラスハミルトニアンにマップする。 最悪な場合、意味保存圧縮を見つける問題は計算的に難しいが、ほぼ最適な性能を実現する効率的なアルゴリズムが存在すると論じる。
  論文  参考訳（メタデータ） (2025-03-01T20:38:16Z)
• Quantize What Counts: More for Keys, Less for Values [63.51476878610841]
  大規模言語モデル(LLM)は、キーバリュー(KV)キャッシュに支配される推論時のメモリボトルネックに悩まされる。 本稿ではトランスフォーマーモデルの内在幾何学における混合精度KV量子化を固定する2つの定理を提案する。
  論文  参考訳（メタデータ） (2025-02-20T22:24:27Z)
• Tree-like process tensor contraction for automated compression of environments [0.0]
  そこで本研究では,PT-MPO縮合の順序を逐次的にツリー様のスキームに変更することにより,ACEの整合性の向上が可能であることを示す。 事前選択手法の欠点は、MPO圧縮が最適以下であり、逐次結合や圧縮よりもエラーの蓄積が多いことである。
  論文  参考訳（メタデータ） (2024-05-26T12:32:57Z)
• Compression of Structured Data with Autoencoders: Provable Benefit of Nonlinearities and Depth [83.15263499262824]
  勾配勾配勾配は入力のスパース構造を完全に無視する解に収束することを示す。 浅層構造にデノナイジング関数を付加することにより,スパースデータの圧縮におけるガウス性能の改善方法を示す。 CIFAR-10 や MNIST などの画像データセットに対して,本研究の成果を検証した。
  論文  参考訳（メタデータ） (2024-02-07T16:32:29Z)
• Combiner: Full Attention Transformer with Sparse Computation Cost [142.10203598824964]
  計算の複雑さを低く保ちつつ、各注目ヘッドにフルアテンション機能を提供するコンバインダを提案する。 既存のスパース変圧器で使用されるスパースアテンションパターンのほとんどは、そのような分解設計をフルアテンションに刺激することができることを示す。 自己回帰的タスクと双方向シーケンスタスクの両方に関する実験的評価は、このアプローチの有効性を示す。
  論文  参考訳（メタデータ） (2021-07-12T22:43:11Z)
• Linear Convergent Decentralized Optimization with Compression [50.44269451541387]
  圧縮を伴う既存の分散アルゴリズムは主にDGD型アルゴリズムの圧縮に焦点を当てている。 原始双対アルゴリズムによって動機付けられた本論文は、最初のアンダーラインLinunderlineEAr収束を提案する。 underline Decentralized with compression, LEAD。
  論文  参考訳（メタデータ） (2020-07-01T04:35:00Z)

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

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