Fugu-MT 論文翻訳(概要): On the Computational Hardness of Transformers

論文の概要: On the Computational Hardness of Transformers

arxiv url: http://arxiv.org/abs/2603.11332v1
Date: Wed, 11 Mar 2026 21:48:43 GMT
ステータス: 翻訳完了
システム内更新日: 2026-03-13 14:46:25.665039
Title: On the Computational Hardness of Transformers
Title（参考訳）: 変圧器の計算硬度について
Abstract要約: この結果から, トランスフォーマーの効率は, 独立評価値のLH$よりも高いことがわかった。小さな埋め込み方式では、$LH$アテンションヘッドは別々に$LHN2 + o(1)$時間を必要とする。大規模な埋め込み方式では、$LHN+ o(1)$算術演算を使用して別々に$LH$アテンションヘッドを計算することができる。
参考スコア（独自算出の注目度）: 14.73362105392153
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The transformer has revolutionized modern AI across language, vision, and beyond. It consists of $L$ layers, each running $H$ attention heads in parallel and feeding the combined output to the subsequent layer. In attention, the input consists of $N$ tokens, each a vector of dimension $m$. The attention mechanism involves multiplying three $N \times m$ matrices, applying softmax to an intermediate product. Several recent works have advanced our understanding of the complexity of attention. Known algorithms for transformers compute each attention head independently. This raises a fundamental question that has recurred throughout TCS under the guise of ``direct sum'' problems: can multiple instances of the same problem be solved more efficiently than solving each instance separately? Many answers to this question, both positive and negative, have arisen in fields spanning communication complexity and algorithm design. Thus, we ask whether transformers can be computed more efficiently than $LH$ independent evaluations of attention. In this paper, we resolve this question in the negative, and give the first non-trivial computational lower bounds for multi-head multi-layer transformers. In the small embedding regime ($m = N^{o(1)}$), computing $LH$ attention heads separately takes $LHN^{2 + o(1)}$ time. We establish that this is essentially optimal under SETH. In the large embedding regime ($m = N$), one can compute $LH$ attention heads separately using $LHN^{ω+ o(1)}$ arithmetic operations (plus exponents), where $ω$ is the matrix multiplication exponent. We establish that this is optimal, by showing that $LHN^{ω- o(1)}$ arithmetic operations are necessary when $ω> 2$. Our lower bound in the large embedding regime relies on a novel application of the Baur-Strassen theorem, a powerful algorithmic tool underpinning the famous backpropagation algorithm.
Abstract（参考訳）: トランスフォーマーは、言語、ビジョン、そしてそれ以上にわたって、現代のAIに革命をもたらした。これは$L$レイヤで構成され、それぞれが$H$アテンションヘッドを並列に実行し、組み合わせた出力を後続のレイヤに供給する。注意点として、入力は$N$トークンで構成され、それぞれが次元$m$のベクトルである。注意機構は、3つの$N \times m$行列を乗算し、中間積にソフトマックスを適用する。いくつかの最近の研究により、注意の複雑さに対する理解が深まった。トランスの既知のアルゴリズムは、それぞれのアテンションヘッドを独立に計算する。これは 'direct sum'' 問題の下でTCS全体で繰り返された根本的な疑問を提起する。同じ問題の複数のインスタンスは、各インスタンスを別々に解決するよりも、より効率的に解決できるのか? この問題に対する多くの答えは、正と負の両方で、コミュニケーションの複雑さとアルゴリズム設計にまたがる分野に現れている。したがって、変換器を$LH$の独立評価よりも効率的に計算できるかどうかを問う。本稿では、この問題を負の形で解決し、マルチヘッド多層トランスにおける最初の非自明な計算下界を与える。小さな埋め込みレジーム(m = N^{o(1)}$)では、$LH$アテンションヘッドは別々に$LHN^{2 + o(1)}$時間を必要とする。これはSETHの下では本質的に最適である。大規模な埋め込みレジーム(m = N$)では、$LHN^{ω+ o(1)}$算術演算(+指数)で別々に$LH$アテンションヘッドを計算できる。 LHN^{ω- o(1)}$算術演算が$ω> 2$のときに必要であることを示すことにより、これが最適であることを示す。我々の大規模な埋め込み体制における下位境界は、有名なバックプロパゲーションアルゴリズムを支える強力なアルゴリズムツールであるバウル・ストラッセンの定理の新たな応用に依存している。

関連論文リスト

Faster quantum linear system solver beyond the condition number [50.84794327094274]
線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
論文参考訳（メタデータ） (2026-07-08T17:49:40Z)
Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure [16.324043075920564]
線形システムと回帰問題を解くための新しい高精度ランダム化アルゴリズムを提供する。我々のアルゴリズムは、これらの問題に対する高密度な入力の下で、自然の複雑さの限界をほぼマッチングする。特異値の$k$を除くすべての値が有界な一般化平均を持つというより弱い仮定の下でも、これらの実行時間を得る方法を示す。
論文参考訳（メタデータ） (2025-07-15T20:48:30Z)
The Oracle Complexity of Simplex-based Matrix Games: Linear Separability and Nash Equilibria [37.300102993926046]
我々は、$max_mathbfwinmathcalWmin_mathbfpinDeltamathbfptopAmathbfw$という形式の行列ゲームを解く問題を研究する。この問題は、線形セパレータの発見やゼロサムゲームにおけるナッシュ平衡の計算といった標準的なタスクをカプセル化する。
論文参考訳（メタデータ） (2024-12-09T20:58:26Z)
Quantum linear system algorithm with optimal queries to initial state preparation [0.0]
線形システムの量子アルゴリズムは、2つのオラクルを問合せして解状態$A-1|brangle$を生成する。本稿では,$mathbfThetaleft (1/sqrtpright)$クエリを$O_b$に変換する量子線形系アルゴリズムを提案する。微分方程式の解法のような様々な応用において、ブロックプレコンディショニングスキームを用いて$p$への依存をさらに改善することができる。
論文参考訳（メタデータ） (2024-10-23T18:00:01Z)
Conv-Basis: A New Paradigm for Efficient Attention Inference and Gradient Computation in Transformers [16.046186753149]
最近のLarge Language Models(LLM)におけるトランスフォーマーの成功の鍵は自己認識メカニズムである我々は、注目行列の畳み込み様構造を利用して、畳み込み行列を用いた注目の効率的な近似法を開発する。トランスフォーマーモデルにおけるアテンション計算を加速するための新しいパラダイムが、より長いコンテキストへのアプリケーションを支援することを願っています。
論文参考訳（メタデータ） (2024-05-08T17:11:38Z)
Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
思考の連鎖(CoT)は、算術や記号的推論タスクにおいて、大きな言語モデル(LLM)の精度を向上させるための非常に効果的な方法である。この研究は、表現性のレンズを通してデコーダのみの変換器に対するCoTのパワーを理論的に理解する。
論文参考訳（メタデータ） (2024-02-20T10:11:03Z)
How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation [12.853829771559916]
本稿では,三重相関を捉える注意の一般化について検討する。この一般化は、変圧器では不可能であった三重結合の検出に関する問題を解くことができる。構築, アルゴリズム, 下位境界が自然に高次テンソルや相関に一般化されることが示される。
論文参考訳（メタデータ） (2023-10-06T07:42:39Z)
Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文参考訳（メタデータ） (2023-07-24T14:37:22Z)
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)
Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。 Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文参考訳（メタデータ） (2022-02-12T21:55:44Z)
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)

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

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