論文の概要: Fundamental Limitations on Subquadratic Alternatives to Transformers

• arxiv url: http://arxiv.org/abs/2410.04271v1
• Date: Sat, 5 Oct 2024 19:21:13 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-02 08:49:52.163155
• Title: Fundamental Limitations on Subquadratic Alternatives to Transformers
• Title（参考訳）: 変圧器の準四角形代替品に関する基礎的限界
• Authors: Josh Alman, Hantao Yu,
• Abstract要約: 文書類似性タスクに重点を置いており、入力された多くの文書として与えられ、最もよく似たペアを見つけたいと思っています。 我々はTransformerがこのタスクを実行できることを証明し、このタスクはどんなアルゴリズムでも真に四分数時間で実行できないことを証明した。
• 参考スコア（独自算出の注目度）: 3.514389461266844
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Transformer architecture is widely deployed in many popular and impactful Large Language Models. At its core is the attention mechanism for calculating correlations between pairs of tokens. Performing an attention computation takes quadratic time in the input size, and had become the time bottleneck for transformer operations. In order to circumvent this, researchers have used a variety of approaches, including designing heuristic algorithms for performing attention computations faster, and proposing alternatives to the attention mechanism which can be computed more quickly. For instance, state space models such as Mamba were designed to replace attention with an almost linear time alternative. In this paper, we prove that any such approach cannot perform important tasks that Transformer is able to perform (assuming a popular conjecture from fine-grained complexity theory). We focus on document similarity tasks, where one is given as input many documents and would like to find a pair which is (approximately) the most similar. We prove that Transformer is able to perform this task, and we prove that this task cannot be performed in truly subquadratic time by any algorithm. Thus, any model which can be evaluated in subquadratic time - whether because of subquadratic-time heuristics for attention, faster attention replacements like Mamba, or any other reason - cannot perform this task. In other words, in order to perform tasks that (implicitly or explicitly) involve document similarity, one may as well use Transformer and cannot avoid its quadratic running time.
• Abstract（参考訳）: Transformerアーキテクチャは、多くの人気で影響力のある大規模言語モデルに広くデプロイされている。 中心となるのは、トークンのペア間の相関を計算するための注意機構である。 注意計算は入力サイズで2次時間を要するようになり、変換器演算の時間ボトルネックとなった。 これを回避するために、研究者は、より高速な注意計算を行うためのヒューリスティックアルゴリズムの設計や、より高速に計算できる注意機構に代わる方法を提案するなど、様々なアプローチを用いてきた。 例えば、Mambaのような状態空間モデルは、注意をほぼ線形時間に置き換えるために設計された。 本稿では,トランスフォーマーが行うことのできる重要なタスクを,そのようなアプローチでは実行できないことを証明する(微粒化複雑性理論からの一般的な予想を仮定する)。 文書類似性タスクは、入力された多くのドキュメントとして与えられ、最も類似した(ほぼ)ペアを見つけたいと思っています。 我々はTransformerがこのタスクを実行できることを証明し、このタスクはどんなアルゴリズムでも真に四分数時間で実行できないことを証明した。 したがって、サブクワッドラティック時間で評価できるモデル – 注意のためのサブクワッドラティック時間ヒューリスティックや、Mambaのようなより高速なアテンション置換など – は、このタスクを実行できない。 言い換えれば、(単純あるいは明示的に)文書の類似性に関わるタスクを実行するためには、Transformerを使うのが適しており、その二次的な実行時間を避けることはできない。

関連論文リスト

• Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Time [17.086679273053853]
  本研究では,新しい高速近似法により,ほぼ線形時間で勾配を計算することができることを示す。 勾配の効率を改善することで、この作業がより効果的なトレーニングと長期コンテキスト言語モデルのデプロイを促進することを期待する。
  論文  参考訳（メタデータ） (2024-08-23T17:16:43Z)
• RankMamba: Benchmarking Mamba's Document Ranking Performance in the Era of Transformers [2.8554857235549753]
  トランスフォーマーアーキテクチャのコアメカニズム -- 注意には、トレーニングにおけるO(n2)$時間複雑さと推論におけるO(n)$時間複雑さが必要です。 状態空間モデルに基づく有名なモデル構造であるMambaは、シーケンスモデリングタスクにおいてトランスフォーマー等価のパフォーマンスを達成した。 同じトレーニングレシピを持つトランスフォーマーベースモデルと比較して,Mambaモデルは競争性能が向上することがわかった。
  論文  参考訳（メタデータ） (2024-03-27T06:07:05Z)
• iTransformer: Inverted Transformers Are Effective for Time Series Forecasting [62.40166958002558]
  iTransformerを提案する。これは、逆次元に注意とフィードフォワードのネットワークを単純に適用する。 iTransformerモデルは、挑戦的な現実世界のデータセットの最先端を実現する。
  論文  参考訳（メタデータ） (2023-10-10T13:44:09Z)
• Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
  本稿では, パール構造因果モデルにおいて, 因果関係などの部分的特定可能なクエリのバウンダリングの問題について議論する。 最近提案された反復EMスキームは初期化パラメータをサンプリングしてそれらの境界を内部近似する。 シンボルパラメータを実際の値に置き換えた回路構造を,単一のシンボル知識コンパイルによって得られることを示す。
  論文  参考訳（メタデータ） (2023-10-05T07:10:40Z)
• Transformers Learn Shortcuts to Automata [52.015990420075944]
  低深度変換器は任意の有限状態オートマトンを計算できる。 我々は,$O(log T)$レイヤを持つ変換器が,長さ$T$の入力シーケンス上で,オートマトンを正確に再現可能であることを示す。 さらに、これらの解の脆性について検討し、潜在的な緩和を提案する。
  論文  参考訳（メタデータ） (2022-10-19T17:45:48Z)
• Predicting Attention Sparsity in Transformers [0.9786690381850356]
  本稿では, 遠心注意の空間パターンを計算前に同定するモデルであるスペーサーファインダーを提案する。 我々の研究は、予測された注目グラフの間隔とリコールの間のトレードオフを広範囲に分析することで、モデル効率を研究するための新しい角度を提供する。
  論文  参考訳（メタデータ） (2021-09-24T20:51:21Z)
• Combiner: Full Attention Transformer with Sparse Computation Cost [142.10203598824964]
  計算の複雑さを低く保ちつつ、各注目ヘッドにフルアテンション機能を提供するコンバインダを提案する。 既存のスパース変圧器で使用されるスパースアテンションパターンのほとんどは、そのような分解設計をフルアテンションに刺激することができることを示す。 自己回帰的タスクと双方向シーケンスタスクの両方に関する実験的評価は、このアプローチの有効性を示す。
  論文  参考訳（メタデータ） (2021-07-12T22:43:11Z)
• Stable, Fast and Accurate: Kernelized Attention with Relative Positional Encoding [63.539333383965726]
  相対的位置符号化(RPE)を用いた変換器の注意計算を高速化する新しい手法を提案する。 相対的な位置符号化がToeplitz行列を形成するという観測に基づいて、Fast Fourier Transform (FFT) を用いて、RPEによるカーネル化された注意を効率的に計算できることを数学的に示す。
  論文  参考訳（メタデータ） (2021-06-23T17:51:26Z)
• The Cascade Transformer: an Application for Efficient Answer Sentence Selection [116.09532365093659]
  本稿では,変圧器をベースとしたモデルのカスケード化手法であるカスケード変換器について紹介する。 現状の変圧器モデルと比較すると,提案手法は精度にほとんど影響を与えずに計算量を37%削減する。
  論文  参考訳（メタデータ） (2020-05-05T23:32:01Z)

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

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