論文の概要: Subquadratic Algorithms and Hardness for Attention with Any Temperature

• arxiv url: http://arxiv.org/abs/2505.14840v1
• Date: Tue, 20 May 2025 19:12:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-22 15:42:58.71836
• Title: Subquadratic Algorithms and Hardness for Attention with Any Temperature
• Title（参考訳）: 準四分法アルゴリズムとどんな温度でも注意すべき硬さ
• Authors: Shreya Gupta, Boyang Huang, Barna Saha, Yinzhan Xu, Christopher Ye,
• Abstract要約: 任意の温度に対する高速な注意が可能である場合の特徴と特徴付けを行う。 アルゴリズムの大幅な改善はありそうにない。 特に、$d = 2Theta(log* n)$ であっても、attention は $n2 - o(1)$time under $mathsfSETH$ を必要とする。
• 参考スコア（独自算出の注目度）: 4.1906341910583045
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Despite the popularity of the Transformer architecture, the standard algorithm for computing Attention suffers from quadratic time complexity in context length $n$. Alman and Song [NeurIPS 2023] showed that when the head dimension $d = \Theta(\log n)$, subquadratic Attention is possible if and only if the inputs have small entries bounded by $B = o(\sqrt{\log n})$ in absolute values, under the Strong Exponential Time Hypothesis ($\mathsf{SETH}$). Equivalently, subquadratic Attention is possible if and only if the softmax is applied with high temperature for $d=\Theta(\log n)$. Running times of these algorithms depend exponentially on $B$ and thus they do not lead to even a polynomial-time algorithm outside the specific range of $B$. This naturally leads to the question: when can Attention be computed efficiently without strong assumptions on temperature? Are there fast attention algorithms that scale polylogarithmically with entry size $B$? In this work, we resolve this question and characterize when fast Attention for arbitrary temperatures is possible. First, for all constant $d = O(1)$, we give the first subquadratic $\tilde{O}(n^{2 - 1/d} \cdot \mathrm{polylog}(B))$ time algorithm for Attention with large $B$. Our result holds even for matrices with large head dimension if they have low rank. In this regime, we also give a similar running time for Attention gradient computation, and therefore for the full LLM training process. Furthermore, we show that any substantial improvement on our algorithm is unlikely. In particular, we show that even when $d = 2^{\Theta(\log^* n)}$, Attention requires $n^{2 - o(1)}$ time under $\mathsf{SETH}$. Finally, in the regime where $d = \mathrm{poly}(n)$, we show that the standard algorithm is optimal under popular fine-grained complexity assumptions.
• Abstract（参考訳）: Transformer アーキテクチャの人気にもかかわらず、Attention の標準的なアルゴリズムはコンテキスト長$n$の2次時間複雑性に悩まされている。 Alman and Song [NeurIPS 2023] は、ヘッド次元 $d = \Theta(\log n)$, subquadratic Attention が可能であるとき、入力が$B = o(\sqrt{\log n})$で有界な小さなエントリを持つ場合に限り、Strong Exponential Time hypothesis ("\mathsf{SETH}$") の下で絶対値を持つことを示した。 同様に、サブクワッドラティックな注意(subquadratic Attention)は、$d=\Theta(\log n)$に対して、ソフトマックスが高温で適用される場合にのみ可能である。 これらのアルゴリズムの実行時間は、指数関数的に$B$に依存しているため、特定の範囲のB$の範囲外の多項式時間アルゴリズムさえも導かない。 温度について強い仮定をすることなく、いつより効率的に注意を計算できるのか? エントリサイズが$B$で多対数的にスケールする高速アテンションアルゴリズムはあるか? 本研究では,この問題を解き,任意の温度に対する高速な注意が可能である場合に特徴付ける。 まず、すべての定数$d = O(1)$に対して、大きな$B$のアテンションに対して最初のサブクワッドラティック $\tilde{O}(n^{2 - 1/d} \cdot \mathrm{polylog}(B))$ time algorithm を与える。 この結果は、低階数である場合、大きな頭部次元を持つ行列に対しても成り立つ。 この方式では、注意勾配計算にも同様の実行時間を与えるので、完全なLLMトレーニングプロセスにも適用できる。 さらに,アルゴリズムの大幅な改善はありそうにないことを示す。 特に、$d = 2^{\Theta(\log^* n)}$であっても、注意には$n^{2 - o(1)}$time under $\mathsf{SETH}$が必要である。 最後に、$d = \mathrm{poly}(n)$ という条件下では、標準アルゴリズムは一般的な微細な複雑性仮定の下で最適であることを示す。

関連論文リスト

• Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point [3.793609515750114]
  我々は、ErdHos-R'enyiランダムグラフのエッジ密度を強く推定する問題を、$G(n, dcirc/n)$で検討する。 我々のアルゴリズムは2乗の総和階層に基づいている。
  論文  参考訳（メタデータ） (2025-03-05T21:45:17Z)
• A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation [6.853165736531941]
  逆数外乱の存在下でのスパース平均推定のアルゴリズム的問題について検討する。 我々の主な貢献は、$mathrmpoly(k,log d,1/epsilon)$サンプルを用いて、エフェサブクアクラティック時間で実行される頑健なスパース平均推定アルゴリズムである。
  論文  参考訳（メタデータ） (2024-03-07T18:23:51Z)
• How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation [12.853829771559916]
  本稿では,三重相関を捉える注意の一般化について検討する。 この一般化は、変圧器では不可能であった三重結合の検出に関する問題を解くことができる。 構築, アルゴリズム, 下位境界が自然に高次テンソルや相関に一般化されることが示される。
  論文  参考訳（メタデータ） (2023-10-06T07:42:39Z)
• Fast Attention Requires Bounded Entries [19.17278873525312]
  内部製品注意計算はTransformer, GPT-1, BERT, GPT-2, GPT-3, ChatGPTなどの大規模言語モデルを訓練するための基本的なタスクである。 行列を暗黙的に$A$とすることで、より高速なアルゴリズムが可能かどうかを検討する。 このことは、入力行列がより小さいエントリを持つ場合、注意計算の方がはるかに効率的である、実際に観察された現象の理論的な説明を与える。
  論文  参考訳（メタデータ） (2023-02-26T02:42:39Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。 また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
  論文  参考訳（メタデータ） (2021-11-09T16:50:18Z)
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
  本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。 複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。 少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
  論文  参考訳（メタデータ） (2021-06-14T07:36: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)

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

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