論文の概要: Circuit Complexity Bounds for RoPE-based Transformer Architecture

• arxiv url: http://arxiv.org/abs/2411.07602v1
• Date: Tue, 12 Nov 2024 07:24:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-13 13:19:27.305155
• Title: Circuit Complexity Bounds for RoPE-based Transformer Architecture
• Title（参考訳）: RoPEを用いた変圧器アーキテクチャのための回路複雑度境界
• Authors: Bo Chen, Xiaoyu Li, Yingyu Liang, Jiangxuan Long, Zhenmei Shi, Zhao Song,
• Abstract要約: 実証的な証拠は、$mathsfRoPE$ベースのTransformerアーキテクチャがより高度な一般化能力を示していることを示唆している。 例えば$mathsfTC0 = mathsfNC1$, $mathsfRoPE$-based Transformer with $mathrmpoly(n)$-precision, $O(1)$ Layer, hidden dimension $d leq O(n)$は算術問題を解くことができないことを示す。
• 参考スコア（独自算出の注目度）: 25.2590541420499
• License:
• Abstract: Characterizing the express power of the Transformer architecture is critical to understanding its capacity limits and scaling law. Recent works provide the circuit complexity bounds to Transformer-like architecture. On the other hand, Rotary Position Embedding ($\mathsf{RoPE}$) has emerged as a crucial technique in modern large language models, offering superior performance in capturing positional information compared to traditional position embeddings, which shows great potential in application prospects, particularly for the long context scenario. Empirical evidence also suggests that $\mathsf{RoPE}$-based Transformer architectures demonstrate greater generalization capabilities compared to conventional Transformer models. In this work, we establish a tighter circuit complexity bound for Transformers with $\mathsf{RoPE}$ attention. Our key contribution is that we show that unless $\mathsf{TC}^0 = \mathsf{NC}^1$, a $\mathsf{RoPE}$-based Transformer with $\mathrm{poly}(n)$-precision, $O(1)$ layers, hidden dimension $d \leq O(n)$ cannot solve the arithmetic problem or the Boolean formula value problem. This result significantly demonstrates the fundamental limitation of the expressivity of the $\mathsf{RoPE}$-based Transformer architecture, although it achieves giant empirical success. Our theoretical framework not only establishes tighter complexity bounds but also may instruct further work on the $\mathsf{RoPE}$-based Transformer.
• Abstract（参考訳）: Transformerアーキテクチャの表現力を特徴付けることは、そのキャパシティ限界とスケーリングの法則を理解するために重要である。 最近の研究は、Transformerのようなアーキテクチャに縛られる回路の複雑さを提供している。 一方、Rotary Position Embedding($\mathsf{RoPE}$)は、現代の大規模言語モデルにおいて重要な技術として登場し、従来の位置情報の埋め込みよりも優れたパフォーマンスを提供する。 経験的証拠は、$\mathsf{RoPE}$-based Transformer アーキテクチャが従来の Transformer モデルと比較してより高度な一般化能力を示していることを示唆している。 本研究では、$\mathsf{RoPE}$ attentionを持つトランスフォーマーに対して、より厳密な回路複雑性を確立する。 我々の重要な貢献は、$\mathsf{TC}^0 = \mathsf{NC}^1$, a $\mathsf{RoPE}$-based Transformer with $\mathrm{poly}(n)$-precision, $O(1)$ layer, hidden dimension $d \leq O(n)$ が算術的問題やブール式値問題を解くことができないことである。 この結果は、巨大な経験的成功にもかかわらず、$\mathsf{RoPE}$ベースのTransformerアーキテクチャの表現性の根本的な制限を示す。 我々の理論フレームワークは、より厳密な複雑性境界を確立するだけでなく、$\mathsf{RoPE}$-based Transformerに関する更なる研究を指示することもできる。

関連論文リスト

• 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)
• Aligning Transformers with Weisfeiler-Leman [5.0452971570315235]
  グラフニューラルネットワークアーキテクチャは、理論的によく理解された表現力を提供する$k$-WL階層と一致している。 我々は,ラプラシアンPEやSPEなどの確立した位置符号化の研究を可能にする理論的枠組みを開発する。 我々は,大規模PCQM4Mv2データセットを用いてトランスフォーマーの評価を行い,最先端のPCQM4Mv2と競合する予測性能を示した。
  論文  参考訳（メタデータ） (2024-06-05T11:06:33Z)
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
  思考の連鎖(CoT)は、算術や記号的推論タスクにおいて、大きな言語モデル(LLM)の精度を向上させるための非常に効果的な方法である。 この研究は、表現性のレンズを通してデコーダのみの変換器に対するCoTのパワーを理論的に理解する。
  論文  参考訳（メタデータ） (2024-02-20T10:11:03Z)
• Transformers Learn Shortcuts to Automata [52.015990420075944]
  低深度変換器は任意の有限状態オートマトンを計算できる。 我々は,$O(log T)$レイヤを持つ変換器が,長さ$T$の入力シーケンス上で,オートマトンを正確に再現可能であることを示す。 さらに、これらの解の脆性について検討し、潜在的な緩和を提案する。
  論文  参考訳（メタデータ） (2022-10-19T17:45:48Z)
• The Parallelism Tradeoff: Limitations of Log-Precision Transformers [29.716269397142973]
  入力トークン数における算術精度が対数的である変換器は、定数深さの対数空間一様しきい値回路でシミュレートできることを示す。 これは、複雑性理論の既知の結果を用いた変圧器のパワーに関する洞察を与える。
  論文  参考訳（メタデータ） (2022-07-02T03:49:34Z)
• Your Transformer May Not be as Powerful as You Expect [88.11364619182773]
  連続列列列関数を近似できるかどうかに関して, RPE ベースの変換器のパワーを数学的に解析する。 RPEをベースとしたトランスフォーマーでは,ニューラルネットワークの深さや幅がどんなに深くても近似できない連続列列列列関数が存在することを示す。 我々は,その条件を満たす,Universal RPE-based (URPE) Attentionと呼ばれる新しいアテンションモジュールを開発する。
  論文  参考訳（メタデータ） (2022-05-26T14:51:30Z)
• Stable, Fast and Accurate: Kernelized Attention with Relative Positional Encoding [63.539333383965726]
  相対的位置符号化(RPE)を用いた変換器の注意計算を高速化する新しい手法を提案する。 相対的な位置符号化がToeplitz行列を形成するという観測に基づいて、Fast Fourier Transform (FFT) を用いて、RPEによるカーネル化された注意を効率的に計算できることを数学的に示す。
  論文  参考訳（メタデータ） (2021-06-23T17:51:26Z)

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

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