論文の概要: Theoretical limitations of multi-layer Transformer

• arxiv url: http://arxiv.org/abs/2412.02975v1
• Date: Wed, 04 Dec 2024 02:37:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-05 15:09:12.610732
• Title: Theoretical limitations of multi-layer Transformer
• Title（参考訳）: 多層変圧器の理論的限界
• Authors: Lijie Chen, Binghui Peng, Hongxun Wu,
• Abstract要約: マルチ層デコーダのみの変換器に対して,最初の$textitunconditional$lowboundを証明した。 また、ある$textitindistinguishable$$textitde$すべての可能な入力を見つける新しい証明手法も導入します。 我々の新しい通信モデルと証明技術は、トランスの計算能力のさらなる理解に役立つと信じている。
• 参考スコア（独自算出の注目度）: 14.63344366356708
• License:
• Abstract: Transformers, especially the decoder-only variants, are the backbone of most modern large language models; yet we do not have much understanding of their expressive power except for the simple $1$-layer case. Due to the difficulty of analyzing multi-layer models, all previous work relies on unproven complexity conjectures to show limitations for multi-layer Transformers. In this work, we prove the first $\textit{unconditional}$ lower bound against multi-layer decoder-only transformers. For any constant $L$, we prove that any $L$-layer decoder-only transformer needs a polynomial model dimension ($n^{\Omega(1)}$) to perform sequential composition of $L$ functions over an input of $n$ tokens. As a consequence, our results give: (1) the first depth-width trade-off for multi-layer transformers, exhibiting that the $L$-step composition task is exponentially harder for $L$-layer models compared to $(L+1)$-layer ones; (2) an unconditional separation between encoder and decoder, exhibiting a hard task for decoders that can be solved by an exponentially shallower and smaller encoder; (3) a provable advantage of chain-of-thought, exhibiting a task that becomes exponentially easier with chain-of-thought. On the technical side, we propose the multi-party $\textit{autoregressive}$ $\textit{communication}$ $\textit{model}$ that captures the computation of a decoder-only Transformer. We also introduce a new proof technique that finds a certain $\textit{indistinguishable}$ $\textit{decomposition}$ of all possible inputs iteratively for proving lower bounds in this model. We believe our new communication model and proof technique will be helpful to further understand the computational power of transformers.
• Abstract（参考訳）: トランスフォーマー、特にデコーダのみの変種は、現代のほとんどの大規模言語モデルのバックボーンである。 多層モデルの解析が難しいため、これまでの研究はすべて、多層トランスフォーマーの限界を示すために、証明されていない複雑性予想に依存していた。 本研究では,最初の$\textit{unconditional}$ lower boundを多層デコーダのみの変換器に対して証明する。 任意の定数$L$に対して、$L$層デコーダのみの変換器は、$n$トークンの入力に対して$L$関数の逐次合成を実行するために多項式モデル次元(n^{\Omega(1)}$)を必要とすることを証明する。 その結果,(1)L$段合成タスクが$(L+1)$層モデルに比べて指数関数的に難しいこと,(2)エンコーダとデコーダの非条件分離,(2)指数関数的に浅いエンコーダと小さいエンコーダで解けるデコーダのハードタスクを示すこと,(3)チェーン・オブ・シークレットの利点を示すこと,などが得られた。 技術的には、デコーダのみのトランスフォーマーの計算をキャプチャするマルチパーティ $\textit{autoregressive}$ $\textit{communication}$ $\textit{model}$を提案する。 また、このモデルで下界を証明するために、可能なすべての入力を反復的に行うために、ある$\textit{indistinguishable}$ $\textit{decomposition}$の証明手法も導入する。 我々の新しい通信モデルと証明技術は、トランスの計算能力のさらなる理解に役立つと信じている。

関連論文リスト

• Circuit Complexity Bounds for RoPE-based Transformer Architecture [25.2590541420499]
  経験的証拠は、$mathsfRoPE$ベースのTransformerアーキテクチャは、従来のTransformerモデルよりも優れた一般化能力を示していることを示している。 我々は、$mathsfTC0 = mathsfNC1$, a $mathsfRoPE$-based Transformer with $mathrmpoly(n)$-precision, $O(1)$ layer, hidden dimension $d leq O(n)$が算術式評価問題を解くことができないことを示す。
  論文  参考訳（メタデータ） (2024-11-12T07:24:41Z)
• On the Role of Depth and Looping for In-Context Learning with Task Diversity [69.4145579827826]
  多様なタスクを伴う線形回帰のための文脈内学習について検討する。 We show that multilayer Transformer is not robust to even distributional shifts as $O(e-L)$ in Wasserstein distance。
  論文  参考訳（メタデータ） (2024-10-29T03:27:56Z)
• Can Transformers Learn $n$-gram Language Models? [77.35809823602307]
  2種類のランダムな$n$-gram LMを学習するトランスフォーマーの能力について検討する。 例えば、$n$-gram LMに対する古典的な推定手法として、add-$lambda$ smoothing outperform transformerがある。
  論文  参考訳（メタデータ） (2024-10-03T21:21:02Z)
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
  思考の連鎖(CoT)は、算術や記号的推論タスクにおいて、大きな言語モデル(LLM)の精度を向上させるための非常に効果的な方法である。 この研究は、表現性のレンズを通してデコーダのみの変換器に対するCoTのパワーを理論的に理解する。
  論文  参考訳（メタデータ） (2024-02-20T10:11:03Z)
• How do Transformers perform In-Context Autoregressive Learning? [76.18489638049545]
  簡単な次のトークン予測タスクでTransformerモデルをトレーニングする。 トレーニングされたTransformerが、まず$W$ in-contextを学習し、次に予測マッピングを適用することで、次のトークンを予測する方法を示す。
  論文  参考訳（メタデータ） (2024-02-08T16:24:44Z)
• Decomposing large unitaries into multimode devices of arbitrary size [0.0]
  複雑なユニタリ進化を一連の構成成分に分解することは、実用的な量子情報処理の基礎となる。 この分解を$mtimes m$ multimode デバイスに一般化する方法を示し、$m>2$である。
  論文  参考訳（メタデータ） (2023-09-21T19:14:39Z)
• Transformers Learn Shortcuts to Automata [52.015990420075944]
  低深度変換器は任意の有限状態オートマトンを計算できる。 我々は,$O(log T)$レイヤを持つ変換器が,長さ$T$の入力シーケンス上で,オートマトンを正確に再現可能であることを示す。 さらに、これらの解の脆性について検討し、潜在的な緩和を提案する。
  論文  参考訳（メタデータ） (2022-10-19T17:45:48Z)
• $O(n)$ Connections are Expressive Enough: Universal Approximability of Sparse Transformers [71.31712741938837]
  注意層ごとに$O(n)$接続しか持たないスパース変換器は、$n2$接続を持つ高密度モデルと同じ関数クラスを近似できることを示す。 また、標準NLPタスクにおいて、異なるパターン・レベルの違いを比較検討する。
  論文  参考訳（メタデータ） (2020-06-08T18:30:12Z)
• Reformer: The Efficient Transformer [21.425616422007543]
  本稿では,トランスフォーマーの効率向上のための2つの手法を提案する。 ドット積の注意を局所性に敏感なハッシュで置き換え、O($L2$) から O($Llog L$) に変更する。 結果のモデルであるReformerはTransformerモデルと同等に動作し、長いシーケンスでははるかにメモリ効率が良く、はるかに高速である。
  論文  参考訳（メタデータ） (2020-01-13T18:38:28Z)

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

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