論文の概要: The I/O Complexity of Attention, or How Optimal is Flash Attention?
- arxiv url: http://arxiv.org/abs/2402.07443v1
- Date: Mon, 12 Feb 2024 06:50:45 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-13 15:20:24.220796
- Title: The I/O Complexity of Attention, or How Optimal is Flash Attention?
- Title（参考訳）: 注意のI/O複雑さ、それともFlashの注意はいかに最適か?
- Authors: Barna Saha, Christopher Ye
- Abstract要約: 自己注意は一般的なTransformerアーキテクチャの中心にあるが、時間とメモリの複雑さに悩まされている。
FlashAttentionアルゴリズムはトランスフォーマーのスケーリングにおける真のボトルネックとしてI/O複雑性を明らかにした。
我々は、FlashAttentionが提供する上限値に一致したI/O複雑性の低いバウンダリを、任意の定数要素内の$M geq d2$の値で示します。
- 参考スコア（独自算出の注目度）: 4.126403496388015
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Self-attention is at the heart of the popular Transformer architecture, yet
suffers from quadratic time and memory complexity. The breakthrough
FlashAttention algorithm revealed I/O complexity as the true bottleneck in
scaling Transformers. Given two levels of memory hierarchy, a fast cache (e.g.
GPU on-chip SRAM) and a slow memory (e.g. GPU high-bandwidth memory), the I/O
complexity measures the number of accesses to memory. FlashAttention computes
attention using $\frac{N^2d^2}{M}$ I/O operations where $N$ is the dimension of
the attention matrix, $d$ the head-dimension and $M$ the cache size. However,
is this I/O complexity optimal? The known lower bound only rules out an I/O
complexity of $o(Nd)$ when $M=\Theta(Nd)$, since the output that needs to be
written to slow memory is $\Omega(Nd)$. This leads to the main question of our
work: Is FlashAttention I/O optimal for all values of $M$?
We resolve the above question in its full generality by showing an I/O
complexity lower bound that matches the upper bound provided by FlashAttention
for any values of $M \geq d^2$ within any constant factors. Further, we give a
better algorithm with lower I/O complexity for $M < d^2$, and show that it is
optimal as well. Moreover, our lower bounds do not rely on using combinatorial
matrix multiplication for computing the attention matrix. We show even if one
uses fast matrix multiplication, the above I/O complexity bounds cannot be
improved. We do so by introducing a new communication complexity protocol for
matrix compression, and connecting communication complexity to I/O complexity.
To the best of our knowledge, this is the first work to establish a connection
between communication complexity and I/O complexity, and we believe this
connection could be of independent interest and will find many more
applications in proving I/O complexity lower bounds in the future.
- Abstract（参考訳）: 自己注意は一般的なTransformerアーキテクチャの中心にあるが、時間とメモリの複雑さに悩まされている。
FlashAttentionアルゴリズムはトランスフォーマーのスケーリングにおける真のボトルネックとしてI/O複雑性を明らかにした。
メモリ階層の2つのレベル、高速キャッシュ(GPUオンチップSRAMなど)と遅いメモリ(GPU高帯域メモリなど)が与えられた場合、I/O複雑性はメモリへのアクセス数を計測する。
flashattentionは$\frac{n^2d^2}{m}$ i/o演算を使ってアテンションを計算し、ここで$n$はアテンション行列の次元、$d$はヘッドディメンション、$m$はキャッシュサイズである。
しかし、このI/O複雑性は最適か?
既知の下限は、メモリを遅くするために書き込む必要のある出力が$\omega(nd)$であるため、$m=\theta(nd)$ のとき、i/o の複雑さが $o(nd)$ となるだけである。
FlashAttention I/Oは$M$のすべての値に最適ですか?
上記の問題を全一般性において解き、任意の定数で$m \geq d^2$の値に対してフラッシュアテンションによって与えられる上限に一致するi/o複雑性下限を示す。
さらに,$M < d^2$に対して,より低いI/O複雑性を持つアルゴリズムを提案し,最適であることを示す。
さらに、我々の下限は、注意行列を計算するのに組合せ行列の乗法を使用しない。
高速な行列乗法を用いても、上記のI/O複雑性境界は改善できない。
我々は,行列圧縮のための新しい通信複雑性プロトコルを導入し,通信複雑性をi/o複雑性に結びつける。
私たちの知る限りでは、これは通信複雑性とI/O複雑性の関連を確立するための最初の取り組みであり、この関係は独立した関心事になり、将来I/O複雑性の低い境界を証明する多くのアプリケーションを見つけるだろうと考えています。
関連論文リスト
- Fast Multipole Attention: A Divide-and-Conquer Attention Mechanism for Long Sequences [1.5484595752241124]
我々は、長さ$n$のシーケンスに対する注意の時間とメモリの複雑さを低減するために、分割・参照戦略を利用する新しい注意機構であるFast Multipole Attentionを提案する。
階層的なアプローチは、クエリ、キー、値を$mathcalO(log n)$の解像度レベルにグループ化する。
我々は,高速多極変換器がメモリサイズや精度の点で,他の効率的な変換器よりもはるかに優れていることを実証的に見出した。
論文 参考訳（メタデータ） (2023-10-18T13:40:41Z) - How to Capture Higher-order Correlations? Generalizing Matrix Softmax
Attention to Kronecker Computation [12.853829771559916]
本稿では,三重相関を捉える注意の一般化について検討する。
この一般化は、変圧器では不可能であった三重結合の検出に関する問題を解くことができる。
構築, アルゴリズム, 下位境界が自然に高次テンソルや相関に一般化されることが示される。
論文 参考訳（メタデータ） (2023-10-06T07:42:39Z) - Cumulative Memory Lower Bounds for Randomized and Quantum Computation [1.52292571922932]
累積記憶は時間空間の複雑さの尺度である。
逐次古典計算と量子回路の両方において、累積メモリの複雑さに関する最初の下位境界を証明した。
論文 参考訳（メタデータ） (2023-01-13T17:57:02Z) - FlashAttention: Fast and Memory-Efficient Exact Attention with
IO-Awareness [80.3586155104237]
FlashAttentionは、トランスフォーマーのためのIO対応の正確な注意アルゴリズムである。
これにより、GPU高帯域メモリ(HBM)とGPUオンチップ間のメモリ読み込み/書き込み数を削減できる。
FlashAttentionとブロックスパース FlashAttentionは、トランスフォーマーのコンテキストを長くすることを可能にする。
論文 参考訳（メタデータ） (2022-05-27T17:53:09Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。
提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
論文 参考訳（メタデータ） (2021-03-03T22:42:15Z) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-18T02:18:44Z) - Approximate Multiplication of Sparse Matrices with Limited Space [24.517908972536432]
我々はスパース共起方向を開発し、期待値の$widetildeOleft((nnz(X)+nnz(Y))ell+nell2right)$に時間複雑性を減少させる。
理論的解析により,我々のアルゴリズムの近似誤差はCODとほぼ同値であることが判明した。
論文 参考訳（メタデータ） (2020-09-08T05:39:19Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。