論文の概要: Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform

• arxiv url: http://arxiv.org/abs/2505.11892v1
• Date: Sat, 17 May 2025 08:03:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-20 14:57:10.919826
• Title: Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform
• Title（参考訳）: 高速RoPE注意:多項式法と高速フーリエ変換を組み合わせる
• Authors: Josh Alman, Zhao Song,
• Abstract要約: トランスフォーマー計算の実行時の主なボトルネックは、アテンション計算と呼ばれるタスクである。 我々はこの問題を克服する方法を示し、RoPEの注意をほぼ線形時間で計算する新しいアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 10.88046646153971
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: The transformer architecture has been widely applied to many machine learning tasks. A main bottleneck in the time to perform transformer computations is a task called attention computation. [Alman and Song, NeurIPS 2023] have shown that in the bounded entry regime, there is an almost linear time algorithm to approximate the attention computation. They also proved that the bounded entry assumption is necessary for a fast algorithm assuming the popular Strong Exponential Time Hypothesis. A new version of transformer which uses position embeddings has recently been very successful. At a high level, position embedding enables the model to capture the correlations between tokens while taking into account their position in the sequence. Perhaps the most popular and effective version is Rotary Position Embedding (RoPE), which was proposed by [Su, Lu, Pan, Murtadha, Wen, and Liu, Neurocomputing 2024]. A main downside of RoPE is that it complicates the attention computation problem, so that previous techniques for designing almost linear time algorithms no longer seem to work. In this paper, we show how to overcome this issue, and give a new algorithm to compute the RoPE attention in almost linear time in the bounded entry regime. (Again, known lower bounds imply that bounded entries are necessary.) Our new algorithm combines two techniques in a novel way: the polynomial method, which was used in prior fast attention algorithms, and the Fast Fourier Transform.
• Abstract（参考訳）: トランスフォーマーアーキテクチャは多くの機械学習タスクに広く適用されている。 トランスフォーマー計算の実行時の主なボトルネックは、アテンション計算と呼ばれるタスクである。 [Alman and Song, NeurIPS 2023] は、有界入力方式では、注意計算を近似するほぼ線形時間アルゴリズムが存在することを示した。 彼らはまた、人気のあるStrong Exponential Time hypothesisを仮定する高速アルゴリズムには、有界なエントリー仮定が必要であることも証明した。 位置埋め込みを利用する新しいバージョンのTransformerは、最近非常に成功した。 高いレベルでは、位置埋め込みにより、モデルは、シーケンスにおけるそれらの位置を考慮してトークン間の相関をキャプチャすることができる。 ロータリー・ポジション・エンベディング(Rotary Position Embedding, RoPE)は[Su, Lu, Pan, Murtadha, Wen, Liu, Neurocomputing 2024]によって提案された。 RoPEの主な欠点は、注意計算問題を複雑にすることで、ほとんど線形時間アルゴリズムを設計する以前の手法がもはや機能しないように見えることである。 本稿では,この問題を克服する方法を示し,制約付きエントリーシステムにおいて,ほぼ線形時間でRoPEの注意を計算するための新しいアルゴリズムを提案する。 (また、既知の下限は、有界な項目が必要であることを暗示している。) 我々の新しいアルゴリズムは、2つの新しい手法を組み合わさり、多項式法は、事前のファストアテンションアルゴリズムに使われ、ファストフーリエ変換(Fast Fourier Transform)が用いられる。

関連論文リスト

• Fast Gradient Computation for RoPE Attention in Almost Linear Time [27.28314860714307]
  我々は,RoPEに基づく有界エントリ下での逆方向の計算のための,最初のニアリニア時間アルゴリズムを開発した。 我々のアプローチは、高速なRoPEアテンション計算の最近の進歩に基づいている。
  論文  参考訳（メタデータ） (2024-12-23T06:20:22Z)
• Optimizing Tensor Computation Graphs with Equality Saturation and Monte Carlo Tree Search [0.0]
  モンテカルロ木探索を用いて優れた表現を構築するテンソルグラフ書き換え手法を提案する。 提案手法は,既存の手法と比較して,ニューラルネットワークの推論速度を最大11%向上させる。
  論文  参考訳（メタデータ） (2024-10-07T22:22:02Z)
• Fundamental Limitations on Subquadratic Alternatives to Transformers [3.514389461266844]
  文書類似性タスクに重点を置いており、入力された多くの文書として与えられ、最もよく似たペアを見つけたいと思っています。 我々はTransformerがこのタスクを実行できることを証明し、このタスクはどんなアルゴリズムでも真に四分数時間で実行できないことを証明した。
  論文  参考訳（メタデータ） (2024-10-05T19:21:13Z)
• Stable, Fast and Accurate: Kernelized Attention with Relative Positional Encoding [63.539333383965726]
  相対的位置符号化(RPE)を用いた変換器の注意計算を高速化する新しい手法を提案する。 相対的な位置符号化がToeplitz行列を形成するという観測に基づいて、Fast Fourier Transform (FFT) を用いて、RPEによるカーネル化された注意を効率的に計算できることを数学的に示す。
  論文  参考訳（メタデータ） (2021-06-23T17:51:26Z)
• Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
  本研究では、重み付き有限状態機械の正規化定数に関する高次微分の計算について検討する。 文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。 我々のアルゴリズムは以前のアルゴリズムよりもはるかに高速である。
  論文  参考訳（メタデータ） (2021-06-01T19:51:55Z)
• 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)
• Quantum-Inspired Classical Algorithm for Principal Component Regression [1.9105479266011323]
  本研究では,データ点数に対して時間的多元対数で動作する主成分回帰のアルゴリズムを開発する。 この指数的なスピードアップは、より大きなデータセットにおける潜在的な応用を可能にする。
  論文  参考訳（メタデータ） (2020-10-16T20:50:48Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

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

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