論文の概要: The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity

• arxiv url: http://arxiv.org/abs/2412.06148v1
• Date: Mon, 09 Dec 2024 02:01:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-10 14:59:01.296684
• Title: The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity
• Title（参考訳）: 回路複雑度レンズによる状態空間モデルとマンバの計算限界
• Authors: Yifang Chen, Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song,
• Abstract要約: 回路複雑性フレームワークを用いて,Mamba と Statespace Models (SSM) の計算限界を解析する。 Mambaのステートフルな設計と、トランスフォーマーを上回る強力な候補として最近注目されているにもかかわらず、$mathsfDLOGTIME$-uniform $mathsfTC0$ complexity classの中に、$mathrmpoly(n)$-precisionと定数深度層を持つMambaとSSMの両方が存在することを実証した。 この結果は、マンバがTransformerと理論的に同じ計算能力を持つことを示し、算術公式問題のような問題を解くことはできない。
• 参考スコア（独自算出の注目度）: 28.909655919558706
• License:
• Abstract: In this paper, we analyze the computational limitations of Mamba and State-space Models (SSMs) by using the circuit complexity framework. Despite Mamba's stateful design and recent attention as a strong candidate to outperform Transformers, we have demonstrated that both Mamba and SSMs with $\mathrm{poly}(n)$-precision and constant-depth layers reside within the $\mathsf{DLOGTIME}$-uniform $\mathsf{TC}^0$ complexity class. This result indicates Mamba has the same computational capabilities as Transformer theoretically, and it cannot solve problems like arithmetic formula problems, boolean formula value problems, and permutation composition problems if $\mathsf{TC}^0 \neq \mathsf{NC}^1$. Therefore, it challenges the assumption Mamba is more computationally expressive than Transformers. Our contributions include rigorous proofs showing that Selective SSM and Mamba architectures can be simulated by $\mathsf{DLOGTIME}$-uniform $\mathsf{TC}^0$ circuits, and they cannot solve problems outside $\mathsf{TC}^0$.
• Abstract（参考訳）: 本稿では,回路複雑性フレームワークを用いて,Mamba と State-space Models (SSM) の計算限界を解析する。 mathrm{poly}(n)$-precision と constant-deepth の2層が $\mathsf{DLOGTIME}$-uniform $\mathsf{TC}^0$ complexity class 内にあることを示した。 この結果は、マンバがTransformerと同じ計算能力を持つことを示し、$\mathsf{TC}^0 \neq \mathsf{NC}^1$の場合、算術公式問題、ブール式値問題、置換合成問題などの問題を解くことはできない。 したがって、Mamba は Transformer よりも計算的に表現できるという仮定に挑戦する。 我々の貢献には、Selective SSM と Mamba のアーキテクチャが $\mathsf{DLOGTIME}$-uniform $\mathsf{TC}^0$ 回路でシミュレート可能であることを示す厳密な証明が含まれている。

関連論文リスト

• The Oracle Complexity of Simplex-based Matrix Games: Linear Separability and Nash Equilibria [37.300102993926046]
  我々は、$max_mathbfwinmathcalWmin_mathbfpinDeltamathbfptopAmathbfw$という形式の行列ゲームを解く問題を研究する。 この問題は、線形セパレータの発見やゼロサムゲームにおけるナッシュ平衡の計算といった標準的なタスクをカプセル化する。
  論文  参考訳（メタデータ） (2024-12-09T20:58:26Z)
• MathGAP: Out-of-Distribution Evaluation on Problems with Arbitrarily Complex Proofs [80.96119560172224]
  MathGAPは、それらの算術的証明構造に関する仕様に従って、問題文と連鎖推論トレースを生成する。 MathGAP を用いて, LLM はより深く, より広くなるにつれて, 性能が著しく低下することがわかった。
  論文  参考訳（メタデータ） (2024-10-17T12:48:14Z)
• Sparse Mamba: Introducing Controllability, Observability, And Stability To Structural State Space Models [2.6353853440763118]
  提案するS-Mambaにおいて,元のMamba SSMアーキテクチャに可制御性と可観測性の概念を導入する。 従来のMambaアーキテクチャの可制御性と可観測性を強化した上で, 難易度を5%改善し, トレーニング時間を3%短縮した。
  論文  参考訳（メタデータ） (2024-08-31T23:25:12Z)
• Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth [8.66267734067296]
  制限しきい値関数を演算する境界を持つ定数深さ回路のクラスについて検討する。 十分大きな$mathsfbPTFC0[k]$の場合、$mathsfbPTFC0[k]は$mathsfTC0[k]を含む。
  論文  参考訳（メタデータ） (2024-08-29T09:40:55Z)
• An Empirical Study of Mamba-based Language Models [69.74383762508805]
  Mambaのような選択的な状態空間モデル(SSM)はトランスフォーマーの欠点を克服する。 同じデータセット上で訓練された8B-context Mamba, Mamba-2, Transformer モデルを直接比較する。 8BのMamba-2-Hybridは、12の標準タスクで8BのTransformerを上回っている。
  論文  参考訳（メタデータ） (2024-06-12T05:25:15Z)
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
  思考の連鎖(CoT)は、算術や記号的推論タスクにおいて、大きな言語モデル(LLM)の精度を向上させるための非常に効果的な方法である。 この研究は、表現性のレンズを通してデコーダのみの変換器に対するCoTのパワーを理論的に理解する。
  論文  参考訳（メタデータ） (2024-02-20T10:11:03Z)
• Is Mamba Capable of In-Context Learning? [63.682741783013306]
  GPT-4のような技術基盤モデルの現状は、文脈内学習(ICL)において驚くほどよく機能する この研究は、新たに提案された状態空間モデルであるMambaが同様のICL能力を持つという実証的な証拠を提供する。
  論文  参考訳（メタデータ） (2024-02-05T16:39:12Z)
• Transformers Learn Shortcuts to Automata [52.015990420075944]
  低深度変換器は任意の有限状態オートマトンを計算できる。 我々は,$O(log T)$レイヤを持つ変換器が,長さ$T$の入力シーケンス上で,オートマトンを正確に再現可能であることを示す。 さらに、これらの解の脆性について検討し、潜在的な緩和を提案する。
  論文  参考訳（メタデータ） (2022-10-19T17:45:48Z)
• Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
  我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。 情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
  論文  参考訳（メタデータ） (2020-12-17T16:43:11Z)
• On the complexity of zero gap MIP* [0.11470070927586014]
  クラス $mathsfMIP*$ が $mathsfRE$ に等しいことを示す。 特にこのことは、非局所ゲーム$G$の量子値の近似の複雑さがハルティング問題の複雑性と同値であることを示している。
  論文  参考訳（メタデータ） (2020-02-24T19:11:01Z)

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

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