論文の概要: The Parallelism Tradeoff: Limitations of Log-Precision Transformers
- arxiv url: http://arxiv.org/abs/2207.00729v4
- Date: Wed, 26 Apr 2023 22:34:12 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-28 17:24:42.856311
- Title: The Parallelism Tradeoff: Limitations of Log-Precision Transformers
- Title(参考訳): 並列性トレードオフ:ログ精度変換器の限界
- Authors: William Merrill and Ashish Sabharwal
- Abstract要約: 入力トークン数における算術精度が対数的である変換器は、定数深さの対数空間一様しきい値回路でシミュレートできることを示す。
これは、複雑性理論の既知の結果を用いた変圧器のパワーに関する洞察を与える。
- 参考スコア(独自算出の注目度): 29.716269397142973
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Despite their omnipresence in modern NLP, characterizing the computational
power of transformer neural nets remains an interesting open question. We prove
that transformers whose arithmetic precision is logarithmic in the number of
input tokens (and whose feedforward nets are computable using space linear in
their input) can be simulated by constant-depth logspace-uniform threshold
circuits. This provides insight on the power of transformers using known
results in complexity theory. For example, if $\mathsf L \neq \mathsf P$ (i.e.,
not all poly-time problems can be solved using logarithmic space), then
transformers cannot even accurately solve linear equalities or check membership
in an arbitrary context-free grammar with empty productions. Our result
intuitively emerges from the transformer architecture's high parallelizability.
We thus speculatively introduce the idea of a fundamental parallelism tradeoff:
any model architecture as parallelizable as the transformer will obey
limitations similar to it. Since parallelism is key to training models at
massive scale, this suggests a potential inherent weakness of the scaling
paradigm.
- Abstract(参考訳): 現代のNLPにおける全知性にもかかわらず、トランスフォーマーニューラルネットの計算能力を特徴づけることは、興味深い疑問である。
入力トークン数で算術精度が対数的である変換器(入力において空間線形で計算可能なフィードフォワードネット)は、定数深さの対数空間一様しきい値回路でシミュレートできることを示す。
これは、複雑性理論の既知の結果を用いた変圧器のパワーに関する洞察を与える。
例えば、$\mathsf L \neq \mathsf P$ (つまり、すべてのポリ時間問題は対数空間で解決できるわけではない) の場合、変換器は任意の文脈自由文法における線形等式を正確に解けない。
我々の結果はトランスアーキテクチャの高並列化性から直感的に現れる。
したがって、我々は基本的な並列性トレードオフの概念を投機的に導入する: トランスフォーマーのように並列化可能なモデルアーキテクチャは、それに似た制限に従う。
大規模モデルのトレーニングには並列性が重要だから,スケーリングパラダイムの潜在的な弱点を示唆するものだ。
関連論文リスト
- Chain of Thought Empowers Transformers to Solve Inherently Serial
Problems [62.91077241315318]
思考の連鎖(CoT)は、算術や記号的推論タスクにおいて、大きな言語モデル(LLM)の精度を向上させるための非常に効果的な方法である。
この研究は、表現性のレンズを通してデコーダのみの変換器に対するCoTのパワーを理論的に理解する。
論文 参考訳(メタデータ) (2024-02-20T10:11:03Z) - Transformers, parallel computation, and logarithmic depth [33.659870765923884]
我々は,一定数の自己注意層が,大規模並列計算の通信ラウンドを効率よくシミュレートし,シミュレートできることを示す。
論文 参考訳(メタデータ) (2024-02-14T15:54:55Z) - Towards Understanding Inductive Bias in Transformers: A View From
Infinity [10.117509279024041]
変換器は、列空間のより置換対称関数に偏りがちである。
対称群の表現論は定量的な解析的予測に利用できることを示す。
我々は、WikiTextデータセットは、実際に置換対称性の程度を持っていると主張している。
論文 参考訳(メタデータ) (2024-02-07T19:00:01Z) - The Expressive Power of Transformers with Chain of Thought [35.25166532364007]
実際には、トランスフォーマーの推論は、答える前に中間トークン列を生成および条件にすることで改善することができる。
答えはYESであるが、増加量は中間生成量に大きく依存する。
また, 線形ステップでは, コンテクストに敏感な言語に変換器デコーダを配置し, 解解時間問題のクラスを正確に認識させる。
論文 参考訳(メタデータ) (2023-10-11T22:35:18Z) - RWKV: Reinventing RNNs for the Transformer Era [54.716108899349614]
本稿では,変換器の効率的な並列化学習とRNNの効率的な推論を組み合わせた新しいモデルアーキテクチャを提案する。
モデルを最大14億のパラメータにスケールし、トレーニングされたRNNの中では最大で、同じサイズのTransformerと同等のRWKVのパフォーマンスを実現しています。
論文 参考訳(メタデータ) (2023-05-22T13:57:41Z) - Transformers Learn Shortcuts to Automata [52.015990420075944]
低深度変換器は任意の有限状態オートマトンを計算できる。
我々は,$O(log T)$レイヤを持つ変換器が,長さ$T$の入力シーケンス上で,オートマトンを正確に再現可能であることを示す。
さらに、これらの解の脆性について検討し、潜在的な緩和を提案する。
論文 参考訳(メタデータ) (2022-10-19T17:45:48Z) - Your Transformer May Not be as Powerful as You Expect [88.11364619182773]
連続列列列関数を近似できるかどうかに関して, RPE ベースの変換器のパワーを数学的に解析する。
RPEをベースとしたトランスフォーマーでは,ニューラルネットワークの深さや幅がどんなに深くても近似できない連続列列列列関数が存在することを示す。
我々は,その条件を満たす,Universal RPE-based (URPE) Attentionと呼ばれる新しいアテンションモジュールを開発する。
論文 参考訳(メタデータ) (2022-05-26T14:51:30Z) - On the Power of Saturated Transformers: A View from Circuit Complexity [87.20342701232869]
飽和変圧器はハードアテンション変圧器の限界を超越していることを示す。
硬度から飽和度へのジャンプは、変換器の有効回路深さを$O(log n)$の係数で増加させると解釈できる。
論文 参考訳(メタデータ) (2021-06-30T17:09:47Z) - Stable, Fast and Accurate: Kernelized Attention with Relative Positional
Encoding [63.539333383965726]
相対的位置符号化(RPE)を用いた変換器の注意計算を高速化する新しい手法を提案する。
相対的な位置符号化がToeplitz行列を形成するという観測に基づいて、Fast Fourier Transform (FFT) を用いて、RPEによるカーネル化された注意を効率的に計算できることを数学的に示す。
論文 参考訳(メタデータ) (2021-06-23T17:51:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。