論文の概要: Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers

• arxiv url: http://arxiv.org/abs/2502.02393v3
• Date: Sat, 12 Jul 2025 18:49:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-15 14:36:06.824416
• Title: Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
• Title（参考訳）: ハードアテンション変圧器のチェーン・オブ・サート共振用下界
• Authors: Alireza Amiri, Xinting Huang, Mark Rofin, Michael Hahn,
• Abstract要約: 整合推論とスクラッチパッドは、変換器の計算能力を高める重要なツールとして登場した。 本研究では,異なるアルゴリズム問題におけるチェーン・オブ・シント・ステップの数に対する体系的下界の研究を開始する。
• 参考スコア（独自算出の注目度）: 5.4649464326326
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Chain-of-thought reasoning and scratchpads have emerged as critical tools for enhancing the computational capabilities of transformers. While theoretical results show that polynomial-length scratchpads can extend transformers' expressivity from $TC^0$ to $PTIME$, their required length remains poorly understood. Empirical evidence even suggests that transformers need scratchpads even for many problems in $TC^0$, such as Parity or Multiplication, challenging optimistic bounds derived from circuit complexity. In this work, we initiate the study of systematic lower bounds for the number of chain-of-thought steps across different algorithmic problems, in the hard-attention regime. We study a variety of algorithmic problems, and provide bounds that are tight up to logarithmic factors. Overall, these results contribute to emerging understanding of the power and limitations of chain-of-thought reasoning.
• Abstract（参考訳）: 整合推論とスクラッチパッドは、変換器の計算能力を高める重要なツールとして登場した。 理論的な結果は、多項式長のスクラッチパッドは変換器の表現性を$TC^0$から$PTIME$に拡張できることを示しているが、必要となる長さは理解されていない。 実証的な証拠は、回路複雑性から導かれる楽観的な境界であるパリティや乗算のようなTC^0$の多くの問題に対しても、変換器がスクラッチパッドを必要とすることを示唆している。 本研究では,異なるアルゴリズム問題におけるチェーン・オブ・シント・ステップの数に対する体系的な下位境界の研究を,ハードアテンション・システマティクスにおいて開始する。 アルゴリズムの様々な問題を研究し、対数的要因に厳密な境界を与える。 全体として、これらの結果は、チェーン・オブ・ソート推論の力と限界の新たな理解に寄与する。

関連論文リスト

• Latent Chain-of-Thought? Decoding the Depth-Recurrent Transformer [0.0]
  CoT(Chain-of- Thought)推論は、トランスフォーマーベースの言語モデルで複雑な数学や多段階計画に優れる。 標準的なデコーダのみのアーキテクチャでは、これらの推論ステップは自然言語で外部化され、効率を犠牲にして解釈性を向上させる。 パラメータ数の増加を伴わずに推論時に層を再利用する深度再帰変換器である Huginn-3.5B にそのような推論構造が出現するかどうかを検討する。
  論文  参考訳（メタデータ） (2025-07-02T23:35:21Z)
• Exact Expressive Power of Transformers with Padding [29.839710738657203]
  長さ$n$の入力に対して$O(logd n)$ループするパッド付き変換器は、適度に並列化可能な問題のクラス$mathsfTCd$を正確に認識する。 この結果から, パディングとループのさらなる探索が, 思考の連鎖に対する並列化可能な代替手段として動機づけられた。
  論文  参考訳（メタデータ） (2025-05-25T02:52:15Z)
• Reasoning by Superposition: A Theoretical Perspective on Chain of Continuous Thought [56.71873693264532]
  連続CoTのD$ステップを持つ2層トランスが有向グラフ到達可能性問題を解くことができることを証明した。 我々の構成では、各連続思考ベクトルは複数の探索フロンティアを同時に符号化する重ね合わせ状態である。
  論文  参考訳（メタデータ） (2025-05-18T18:36:53Z)
• Compositional Reasoning with Transformers, RNNs, and Chain of Thought [38.651863218241154]
  我々は、構成推論質問(CRQ)と呼ばれる単純で自然な問題に対して、変換器、RNN、変換器の表現力と思考トークンの連鎖を比較し、比較する。 このファミリーはブール式の評価や多段階語問題などの問題を捉えている。
  論文  参考訳（メタデータ） (2025-03-03T13:52:45Z)
• 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 Looped Transformers Learn to Implement Multi-step Gradient Descent for In-context Learning? [69.4145579827826]
  収束ランドスケープの勾配非性アルゴリズムにもかかわらず、回帰損失に高速な流れを示す。 この設定における多層トランスの理論的解析はこれが初めてである。
  論文  参考訳（メタデータ） (2024-10-10T18:29:05Z)
• 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)

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

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