論文の概要: Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization

• arxiv url: http://arxiv.org/abs/2511.07378v1
• Date: Mon, 10 Nov 2025 18:40:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-11 21:18:45.413772
• Title: Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization
• Title（参考訳）: 変圧器は長大一般化によるチェーン・オブ・ソート推論を確実に学習する
• Authors: Yu Huang, Zixin Wen, Aarti Singh, Yuejie Chi, Yuxin Chen,
• Abstract要約: AI推論に関する重要な問題は、モデルが学習した推論パターンを外挿して、より長いチェーン・オブ・シークレット(CoT)で難しいタスクを解決できるかどうかである。 状態追跡問題の代数構造が、学習されたCoTの外挿の度合いをいかに支配するかを数学的に証明する。 定数深度変換器はCoTで$mathsfNC1$-complete問題を確実に学習することを保証する。
• 参考スコア（独自算出の注目度）: 53.89723291716722
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The ability to reason lies at the core of artificial intelligence (AI), and challenging problems usually call for deeper and longer reasoning to tackle. A crucial question about AI reasoning is whether models can extrapolate learned reasoning patterns to solve harder tasks with longer chain-of-thought (CoT). In this work, we present a theoretical analysis of transformers learning on synthetic state-tracking tasks with gradient descent. We mathematically prove how the algebraic structure of state-tracking problems governs the degree of extrapolation of the learned CoT. Specifically, our theory characterizes the length generalization of transformers through the mechanism of attention concentration, linking the retrieval robustness of the attention layer to the state-tracking task structure of long-context reasoning. Moreover, for transformers with limited reasoning length, we prove that a recursive self-training scheme can progressively extend the range of solvable problem lengths. To our knowledge, we provide the first optimization guarantee that constant-depth transformers provably learn $\mathsf{NC}^1$-complete problems with CoT, significantly going beyond prior art confined in $\mathsf{TC}^0$, unless the widely held conjecture $\mathsf{TC}^0 \neq \mathsf{NC}^1$ fails. Finally, we present a broad set of experiments supporting our theoretical results, confirming the length generalization behaviors and the mechanism of attention concentration.
• Abstract（参考訳）: 推論する能力は人工知能(AI)の中核にある。 AI推論に関する重要な問題は、学習した推論パターンを外挿して、より長いチェーン・オブ・シークレット(CoT)で難しいタスクを解決できるかどうかである。 そこで本研究では,勾配降下を伴う状態追跡タスクを学習する変圧器の理論解析を行った。 状態追跡問題の代数構造が、学習されたCoTの外挿の度合いをいかに支配するかを数学的に証明する。 具体的には,アテンション集中機構によるトランスフォーマーの長さ一般化を特徴付け,アテンション層の検索ロバスト性と長文推論の状態追跡タスク構造を関連付ける。 さらに, 推論長が制限された変圧器に対しては, 再帰的自己学習スキームが解ける問題長の範囲を徐々に拡張できることを示す。 我々の知る限り、定数深度変換器はCoTで証明的に$\mathsf{NC}^1$-完全問題を学習し、広く知られている予想である$\mathsf{TC}^0 \neq \mathsf{NC}^1$が失敗しない限り、$\mathsf{TC}^0$に制限された先行技術を超えることを保証している。 最後に、我々の理論結果を支持する実験の幅広いセットを示し、長さ一般化の挙動と注意集中のメカニズムを確認した。

関連論文リスト

• Quantitative Bounds for Length Generalization in Transformers [58.175107357008876]
  変圧器における長さ一般化(LG)問題について検討する。 LGは、長い列上の変圧器の内部挙動が短い列上の振舞いによって「シミュレート」できるときに発生する。
  論文  参考訳（メタデータ） (2025-10-30T21:31:36Z)
• The Imitation Game: Turing Machine Imitator is Length Generalizable Reasoner [71.41162392872393]
  本稿では,大規模言語モデルの長さ一般化能力を向上させるため,Turing Machine Imitation Learning (TAIL)を提案する。 TAILはコンピュータプログラムによってチューリングマシンの実行プロセスを模倣するチェーン・オブ・思想(CoT)データを合成する。 ベルとホイッスルがなければ、TAILは様々なタスクにおけるQwen2.5-7Bの性能と同様に、長さの一般化能力を大幅に改善する。
  論文  参考訳（メタデータ） (2025-07-17T17:50:07Z)
• Training Nonlinear Transformers for Chain-of-Thought Inference: A Theoretical Generalization Analysis [82.51626700527835]
  チェーン・オブ・シフト(Chain-of-shift, CoT)は、複数の中間ステップを持つ例を用いてクエリを増強することにより、大規模言語モデルの推論能力を実現する効率的な手法である。 CoT の理論的成功にもかかわらず、CoT が成立しても正確な一般化が得られないことを示す。
  論文  参考訳（メタデータ） (2024-10-03T03:12:51Z)
• Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective [39.47116013338394]
  CoT(Chain-of-Thought prompting)は,大規模言語モデル(LLM)の性能を劇的に向上させる 我々は、CoTが動的プログラミング(Dynamic Programming)として知られる一般的な意思決定問題に対処できることを示します。
  論文  参考訳（メタデータ） (2023-05-24T17:59:21Z)

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

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