論文の概要: How Sparse Attention Approximates Exact Attention? Your Attention is Naturally $n^C$-Sparse
- arxiv url: http://arxiv.org/abs/2404.02690v2
- Date: Wed, 12 Feb 2025 14:32:46 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-13 13:47:24.097067
- Title: How Sparse Attention Approximates Exact Attention? Your Attention is Naturally $n^C$-Sparse
- Title（参考訳）: あなたの注意は自然に$n^C$-sparseである。
- Authors: Yichuan Deng, Zhao Song, Jing Xiong, Chiwun Yang,
- Abstract要約: スパース注意(英: Sparse Attention)とは、標準的な注意計算と準四分法的な複雑性を近似する手法である。
KVキャッシュのプルーニング、スパースベースの高速注意、スパーストランスフォーマーといったテクニックのバリエーションは、効率的なLLM(Large Language Models)デプロイメントに広く利用されている。
- 参考スコア（独自算出の注目度）: 9.552839922307587
- License:
- Abstract: Sparse Attention is a technique that approximates standard attention computation with sub-quadratic complexity. This is achieved by selectively ignoring smaller entries in the attention matrix during the softmax function computation. Variations of this technique, such as pruning KV cache, sparsity-based fast attention, and Sparse Transformer, have been extensively utilized for efficient Large Language Models (LLMs) deployment. Despite its widespread use, a theoretical understanding of the conditions under which sparse attention performs on par with traditional attention remains elusive. This work aims to $\textbf{bridge this gap by examining the inherent sparsity of standard attention processes}$. Our theoretical framework reveals several brand-new key insights: $\bullet$ Attention is $n^{C}$-sparse, implying that considering only the largest $\Omega(n^{C})$ entries out of all $n$ entries is sufficient for sparse attention to approximate the exact attention matrix with decreasing loss. Here, $n$ represents the input length and $C \in (0, 1)$ is a constant. $\bullet$ Stable $o(\log(n))$-sparse attention, which approximates attention computation with $\log(n)$ or fewer entries, may not be feasible since the error will persist at a minimum of $O(1)$. $\bullet$ An adaptive strategy ($\alpha \cdot n^C, \alpha \in \mathbb{R}$) for the window size of efficient attention methods rather than a fixed one is guaranteed to perform more accurately and efficiently in a task for inference on flexible context lengths.
- Abstract（参考訳）: スパース注意(英: Sparse Attention)とは、標準的な注意計算と準四分法的な複雑性を近似する手法である。
これは、ソフトマックス関数計算中に注意行列の小さいエントリを選択的に無視することで達成される。
KVキャッシュのプルーニング、スパースベースの高速注意、スパーストランスフォーマーといったテクニックのバリエーションは、効率的なLLM(Large Language Models)デプロイメントに広く利用されている。
広く使われているにもかかわらず、希少な注意が従来の注意と同等に作用する条件に関する理論的理解はいまだに解明されていない。
この作業は、標準の注意プロセスの本質的な間隔を調べて、このギャップを$\textbf{bridge することを目的としています。
我々の理論フレームワークは、いくつかの新しい重要な洞察を明らかにしている: $\bullet$ Attention is $n^{C}$-sparse は、すべての$n$エントリのうち、最大$\Omega(n^{C})$エントリだけを考えると、損失を減少させて正確な注意行列を近似するのに十分であることを意味する。
ここで、$n$は入力長を表し、$C \in (0, 1)$は定数である。
$\bullet$ Stable $o(\log(n))$-sparse attentionは、注意計算を$\log(n)$以下で近似する。
$\bullet$ 適応戦略(\alpha \cdot n^C, \alpha \in \mathbb{R}$)は、柔軟なコンテキスト長の推論タスクにおいて、より正確に効率的に実行することを保証している。
関連論文リスト
- LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
任意の$K$に対して、$n$とは独立に「普遍集合」$Uサブセット[n]$が存在し、任意の$Q$と任意の行$i$に対して、大きな注目スコアが$A_i,j$ in row $i$ of $A$は全て$jin U$を持つことを示す。
我々は、視覚変換器のスキームの利点を実証的に示し、トレーニング中に我々の普遍的なセットを使用する新しいモデルのトレーニング方法を示した。
論文 参考訳（メタデータ） (2024-10-07T19:47:13Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Conv-Basis: A New Paradigm for Efficient Attention Inference and Gradient Computation in Transformers [16.046186753149]
最近のLarge Language Models(LLM)におけるトランスフォーマーの成功の鍵は自己認識メカニズムである
我々は、注目行列の畳み込み様構造を利用して、畳み込み行列を用いた注目の効率的な近似法を開発する。
トランスフォーマーモデルにおけるアテンション計算を加速するための新しいパラダイムが、より長いコンテキストへのアプリケーションを支援することを願っています。
論文 参考訳（メタデータ） (2024-05-08T17:11:38Z) - 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) - How to Capture Higher-order Correlations? Generalizing Matrix Softmax
Attention to Kronecker Computation [12.853829771559916]
本稿では,三重相関を捉える注意の一般化について検討する。
この一般化は、変圧器では不可能であった三重結合の検出に関する問題を解くことができる。
構築, アルゴリズム, 下位境界が自然に高次テンソルや相関に一般化されることが示される。
論文 参考訳（メタデータ） (2023-10-06T07:42:39Z) - Randomized and Deterministic Attention Sparsification Algorithms for
Over-parameterized Feature Dimension [18.57735939471469]
我々は注意問題のスパシフィケーションを考慮する。
超大規模特徴量の場合、文の長さをほぼ線形に縮めることができる。
論文 参考訳（メタデータ） (2023-04-10T05:52:38Z) - Fast Attention Requires Bounded Entries [19.17278873525312]
内部製品注意計算はTransformer, GPT-1, BERT, GPT-2, GPT-3, ChatGPTなどの大規模言語モデルを訓練するための基本的なタスクである。
行列を暗黙的に$A$とすることで、より高速なアルゴリズムが可能かどうかを検討する。
このことは、入力行列がより小さいエントリを持つ場合、注意計算の方がはるかに効率的である、実際に観察された現象の理論的な説明を与える。
論文 参考訳（メタデータ） (2023-02-26T02:42:39Z) - Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。
本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
論文 参考訳（メタデータ） (2023-02-22T20:21:25Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳（メタデータ） (2021-05-17T16:40:48Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。
最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文 参考訳（メタデータ） (2020-03-04T07:36:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。