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

• arxiv url: http://arxiv.org/abs/2411.07602v2
• Date: Sun, 01 Dec 2024 06:39:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-03 16:56:58.295042
• 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アーキテクチャは、従来のTransformerモデルよりも優れた一般化能力を示していることを示している。 我々は、$mathsfTC0 = mathsfNC1$, a $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 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 formula evaluation 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 result not only establishes the complexity bound 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に関するさらなる研究を指示することもできる。

関連論文リスト

• Theoretical Constraints on the Expressive Power of $\mathsf{RoPE}$-based Tensor Attention Transformers [23.991344681741058]
  本研究では, アテンションと$mathsfRoPE$-based Attentionの回路複雑性を分析し, 固定メンバシップ問題や$(A_F,r)*$クロージャ問題を解くことができないことを示す。 これらの結果は,経験的性能と注意の理論的制約と$mathsfRoPE$ベースの注意変換器とのギャップを浮き彫りにした。
  論文  参考訳（メタデータ） (2024-12-23T23:26:07Z)
• Theoretical limitations of multi-layer Transformer [14.63344366356708]
  マルチ層デコーダのみの変換器に対して,最初の$textitunconditional$lowboundを証明した。 また、ある$textitindistinguishable$$textitde$すべての可能な入力を見つける新しい証明手法も導入します。 我々の新しい通信モデルと証明技術は、トランスの計算能力のさらなる理解に役立つと信じている。
  論文  参考訳（メタデータ） (2024-12-04T02:37:31Z)
• 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)
• 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)

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

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