論文の概要: Compositional Reasoning with Transformers, RNNs, and Chain of Thought

• arxiv url: http://arxiv.org/abs/2503.01544v1
• Date: Mon, 03 Mar 2025 13:52:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-05 19:26:35.055089
• Title: Compositional Reasoning with Transformers, RNNs, and Chain of Thought
• Title（参考訳）: 変圧器, RNN, および思考の連鎖による構成的推論
• Authors: Gilad Yehudai, Noah Amsel, Joan Bruna,
• Abstract要約: 我々は、構成推論質問(CRQ)と呼ばれる単純で自然な問題に対して、変換器、RNN、変換器の表現力と思考トークンの連鎖を比較し、比較する。 このファミリーはブール式の評価や多段階語問題などの問題を捉えている。
• 参考スコア（独自算出の注目度）: 38.651863218241154
• License:
• Abstract: We study and compare the expressive power of transformers, RNNs, and transformers with chain of thought tokens on a simple and natural class of problems we term Compositional Reasoning Questions (CRQ). This family captures problems like evaluating Boolean formulas and multi-step word problems. Assuming standard hardness assumptions from circuit complexity and communication complexity, we prove that none of these three architectures is capable of solving CRQs unless some hyperparameter (depth, embedding dimension, and number of chain of thought tokens, respectively) grows with the size of the input. We also provide a construction for each architecture that solves CRQs. For transformers, our construction uses depth that is logarithmic in the problem size. For RNNs, logarithmic embedding dimension is necessary and sufficient, so long as the inputs are provided in a certain order. (Otherwise, a linear dimension is necessary). For transformers with chain of thought, our construction uses $n$ CoT tokens. These results show that, while CRQs are inherently hard, there are several different ways for language models to overcome this hardness. Even for a single class of problems, each architecture has strengths and weaknesses, and none is strictly better than the others.
• Abstract（参考訳）: 本研究では,変換器,RNN,変換器の表現力と,合成推論質問 (CRQ) と呼ばれる,単純で自然な問題に対する思考トークンの連鎖について検討し,比較する。 このファミリーはブール式の評価や多段階語問題などの問題を捉えている。 回路の複雑さと通信の複雑さから標準的な硬さの仮定を仮定すると、これらの3つのアーキテクチャのうちのどのアーキテクチャも、いくつかのハイパーパラメータ(深度、埋め込み次元、思考トークンの鎖数)が入力の大きさで増加しない限り、CRQを解くことができないことが証明される。 また、CRQを解く各アーキテクチャの構成も提供します。 変圧器の場合、我々の構成では問題の大きさの対数的な深さを用いる。 RNNにとって、入力が一定の順序で提供される限り、対数埋め込み次元は必要で十分である。 (また、線型次元も必要) 思考の連鎖を持つ変換器の場合、我々の構成は$n$CoTトークンを使用する。 これらの結果は、CRQは本質的に難しいが、言語モデルがこの難しさを克服する方法がいくつか存在することを示している。 単一レベルの問題であっても、それぞれのアーキテクチャには長所と短所があり、他のどのアーキテクチャよりも厳格に優れているものはありません。

関連論文リスト

• Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers [5.4649464326326]
  整合推論とスクラッチパッドは、変換器の計算能力を高める重要なツールとして登場した。 本研究では,異なるアルゴリズム問題にまたがるCoTステップ数に対する体系的下界の研究を開始する。
  論文  参考訳（メタデータ） (2025-02-04T15:14:01Z)
• Transformers are Efficient Compilers, Provably [11.459397066286822]
  トランスフォーマーベースの大規模言語モデル(LLM)は、幅広い言語関連タスクにおいて驚くほど堅牢なパフォーマンスを示している。 本稿では,表現力の観点から,トランスフォーマーをコンパイラとして用いることの正式な調査に向けて第一歩を踏み出す。 代表言語であるMini-Huskyを導入し、現代のC言語の特徴をカプセル化する。
  論文  参考訳（メタデータ） (2024-10-07T20:31:13Z)
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
  思考の連鎖(CoT)は、算術や記号的推論タスクにおいて、大きな言語モデル(LLM)の精度を向上させるための非常に効果的な方法である。 この研究は、表現性のレンズを通してデコーダのみの変換器に対するCoTのパワーを理論的に理解する。
  論文  参考訳（メタデータ） (2024-02-20T10:11:03Z)
• The Expressive Power of Transformers with Chain of Thought [29.839710738657203]
  実際には、トランスフォーマーは「思考の連鎖」や「スクラッチパッド」を使用することで改善できる。 答えはYESであるが、増加量は中間生成量に大きく依存する。 また, 線形ステップでは, コンテクストに敏感な言語に変換器デコーダを配置することが示唆された。
  論文  参考訳（メタデータ） (2023-10-11T22:35:18Z)
• Faith and Fate: Limits of Transformers on Compositionality [109.79516190693415]
  3つの代表的構成課題にまたがる変圧器大言語モデルの限界について検討する。 これらのタスクは、問題をサブステップに分割し、これらのステップを正確な答えに合成する必要があります。 実験結果から,多段階合成推論を線形化部分グラフマッチングに還元することにより,トランスフォーマーLLMが構成課題を解くことが示唆された。
  論文  参考訳（メタデータ） (2023-05-29T23:24:14Z)
• 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)
• On the Power of Saturated Transformers: A View from Circuit Complexity [87.20342701232869]
  飽和変圧器はハードアテンション変圧器の限界を超越していることを示す。 硬度から飽和度へのジャンプは、変換器の有効回路深さを$O(log n)$の係数で増加させると解釈できる。
  論文  参考訳（メタデータ） (2021-06-30T17:09:47Z)
• Thinking Like Transformers [64.96770952820691]
  本稿では,プログラミング言語の形式で変換器エンコーダの計算モデルを提案する。 RASPは、トランスフォーマーによって確実に学習できるタスクの解決策をプログラムするのにどのように使えるかを示す。 ヒストグラム、ソート、ダイク言語のためのRASPプログラムを提供する。
  論文  参考訳（メタデータ） (2021-06-13T13:04:46Z)

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

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