論文の概要: Conv-Basis: A New Paradigm for Efficient Attention Inference and Gradient Computation in Transformers
- arxiv url: http://arxiv.org/abs/2405.05219v1
- Date: Wed, 8 May 2024 17:11:38 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-09 13:55:22.236372
- Title: Conv-Basis: A New Paradigm for Efficient Attention Inference and Gradient Computation in Transformers
- Title（参考訳）: Conv-Basis: 変圧器の効率的な注意推論と勾配計算のための新しいパラダイム
- Authors: Jiuxiang Gu, Yingyu Liang, Heshan Liu, Zhenmei Shi, Zhao Song, Junze Yin,
- Abstract要約: 我々は、注目行列の畳み込み様構造を利用して、畳み込み行列を用いた注目の効率的な近似法を開発する。
我々のアルゴリズムは、ほぼ線形時間、すなわち$n1+o(1)$を達成する。
この作業は、アプリケーションがより長いコンテキストに到達できるように、トランスフォーマーにおける注意計算を加速するための新しいパラダイムを提供する。
- 参考スコア（独自算出の注目度）: 27.54512534985192
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Large Language Models (LLMs) have profoundly changed the world. Their self-attention mechanism is the key to the success of transformers in LLMs. However, the quadratic computational cost $O(n^2)$ to the length $n$ input sequence is the notorious obstacle for further improvement and scalability in the longer context. In this work, we leverage the convolution-like structure of attention matrices to develop an efficient approximation method for attention computation using convolution matrices. We propose a $\mathsf{conv}$ basis system, "similar" to the rank basis, and show that any lower triangular (attention) matrix can always be decomposed as a sum of $k$ structured convolution matrices in this basis system. We then design an algorithm to quickly decompose the attention matrix into $k$ convolution matrices. Thanks to Fast Fourier Transforms (FFT), the attention {\it inference} can be computed in $O(knd \log n)$ time, where $d$ is the hidden dimension. In practice, we have $ d \ll n$, i.e., $d=3,072$ and $n=1,000,000$ for Gemma. Thus, when $kd = n^{o(1)}$, our algorithm achieve almost linear time, i.e., $n^{1+o(1)}$. Furthermore, the attention {\it training forward} and {\it backward gradient} can be computed in $n^{1+o(1)}$ as well. Our approach can avoid explicitly computing the $n \times n$ attention matrix, which may largely alleviate the quadratic computational complexity. Furthermore, our algorithm works on any input matrices. This work provides a new paradigm for accelerating attention computation in transformers to enable their application to longer contexts.
- Abstract（参考訳）: 大きな言語モデル(LLM)は世界を大きく変えました。
自己保持機構は、LSMにおけるトランスフォーマーの成功の鍵となる。
しかし、2次計算コスト$O(n^2)$から$n$の入力シーケンスは、より長いコンテキストにおいてさらなる改善とスケーラビリティの障害として悪名高い。
本研究では,注目行列の畳み込み様構造を利用して,畳み込み行列を用いた注目計算の効率的な近似法を開発する。
我々は、階数基底に類似した$\mathsf{conv}$基底系を提案し、この基底系において、下方三角形(アテンション)行列は常に$k$構造化畳み込み行列の和として分解可能であることを示す。
次に、注目行列を高速に$k$畳み込み行列に分解するアルゴリズムを設計する。
Fast Fourier Transforms (FFT)により、注目度は$O(knd \log n)$ timeで計算できる。
実際、$ d \ll n$ すなわち $d=3,072$ と $n=1,000,000$ が Gemma に対して成り立つ。
したがって、$kd = n^{o(1)}$の場合、我々のアルゴリズムはほぼ線形時間、すなわち$n^{1+o(1)}$を達成する。
さらに、注意 {\it training forward} と {\it backward gradient} も$n^{1+o(1)}$で計算できる。
我々のアプローチでは、$n \times n$ attention matrix を明示的に計算することができない。
さらに,アルゴリズムは任意の入力行列に作用する。
この作業は、アプリケーションがより長いコンテキストに到達できるように、トランスフォーマーにおける注意計算を加速するための新しいパラダイムを提供する。
関連論文リスト
- 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) - Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems [9.30306458153248]
我々は、スペクトルテール条件数である$kappa_ell$を、システムを表す行列の最小特異値と$ell$2の比として定義する。
結果のいくつかの意味と$kappa_ell$の使用は、Conjugateメソッドのきめ細かい解析を直接改善することを含んでいる。
論文 参考訳（メタデータ） (2024-05-09T14:56:49Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - How to Capture Higher-order Correlations? Generalizing Matrix Softmax
Attention to Kronecker Computation [12.853829771559916]
本稿では,三重相関を捉える注意の一般化について検討する。
この一般化は、変圧器では不可能であった三重結合の検出に関する問題を解くことができる。
構築, アルゴリズム, 下位境界が自然に高次テンソルや相関に一般化されることが示される。
論文 参考訳（メタデータ） (2023-10-06T07:42:39Z) - Scalable First-Order Bayesian Optimization via Structured Automatic
Differentiation [4.061135251278187]
広い範囲のカーネルが構造化行列を生じさせ、勾配観測のための正確な$mathcalO(n2d)$Matrix-vector multiplyとヘッセン観測のための$mathcalO(n2d2)$を可能にした。
提案手法は,ほぼすべての標準カーネルに適用され,ニューラルネットワーク,放射基底関数ネットワーク,スペクトル混合カーネルなどの複雑なカーネルに自動的に拡張される。
論文 参考訳（メタデータ） (2022-06-16T17:59:48Z) - Fast Differentiable Matrix Square Root [65.67315418971688]
微分可能な行列平方根を計算するために、より効率的な2つの変種を提案する。
前方伝播には, Matrix Taylor Polynomial (MTP) を用いる方法がある。
もう1つの方法は Matrix Pad'e Approximants (MPA) を使うことである。
論文 参考訳（メタデータ） (2022-01-21T12:18:06Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Constant-Depth and Subcubic-Size Threshold Circuits for Matrix
Multiplication [1.9518237361775532]
大規模ニューラルネットワークハードウェアの最近の進歩は、その実践的実装を短期的可能性にしている。
しきい値ゲート論理を統合する2つの$N$を$N$行列に乗算する理論的アプローチについて述べる。
デンス行列乗算は畳み込みニューラルネットワークトレーニングにおけるコア演算である。
論文 参考訳（メタデータ） (2020-06-25T18:28:10Z) - Fast Matrix Square Roots with Applications to Gaussian Processes and
Bayesian Optimization [24.085358075449406]
行列平方根とその逆は機械学習で頻繁に現れる。
我々は,$mathbf K1/2 mathbf b$,$mathbf K-1/2 mathbf b$とその導関数を行列ベクトル乗算(MVM)により計算するための高効率二次時間アルゴリズムを導入する。
提案手法は,Krylov部分空間法と有理近似,典型的には4ドル10分の精度で100ドル未満のMVMを推定する。
論文 参考訳（メタデータ） (2020-06-19T17:56:24Z) - Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。
代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
論文 参考訳（メタデータ） (2020-06-12T10:21:40Z) - Sketching Transformed Matrices with Applications to Natural Language
Processing [76.6222695417524]
本稿では, 変換行列を用いて, 与えられた小さな行列の積を計算するための空間効率のよいスケッチアルゴリズムを提案する。
提案手法は誤差が小さく,空間と時間の両方で効率がよいことを示す。
論文 参考訳（メタデータ） (2020-02-23T03:07:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。