論文の概要: Barriers to Universal Reasoning With Transformers (And How to Overcome Them)

• arxiv url: http://arxiv.org/abs/2604.25800v1
• Date: Tue, 28 Apr 2026 16:10:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-29 16:49:17.941185
• Title: Barriers to Universal Reasoning With Transformers (And How to Overcome Them)
• Title（参考訳）: トランスフォーマーと共謀するバリアたち(そして克服する方法)
• Abstract要約: CoT(Chain-of-Thought)は、トランスフォーマーの性能を実証的に改善し、理論的にはチューリング完全性への表現性を高めることが示されている。 我々は、Transformer長の一般化に関する最近の理論フレームワークを使用し、標準的な位置エンコーディングと有限アルファベットの下では、CoT を持つ変換器は$TC0$以上の問題を解くことができない。 我々は,シミュレーション実行時のCoTトレース長が一定まで線形であるチューリングマシンの時間一般化可能なシミュレーションを実現する。
• 参考スコア（独自算出の注目度）: 46.59247939156339
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Chain-of-Thought (CoT) has been shown to empirically improve Transformers' performance, and theoretically increase their expressivity to Turing completeness. However, whether Transformers can learn to generalize to CoT traces longer than those seen during training is understudied. We use recent theoretical frameworks for Transformer length generalization and find that -- under standard positional encodings and a finite alphabet -- Transformers with CoT cannot solve problems beyond $TC^0$, i.e. the expressivity benefits do not hold under the stricter requirement of length-generalizable learnability. However, if we allow the vocabulary to grow with problem size, we attain a length-generalizable simulation of Turing machines where the CoT trace length is linear in the simulated runtime up to a constant. Our construction overcomes two core obstacles to reliable length generalization: repeated copying and last-occurrence retrieval. We assign each tape position a unique signpost token, and log only value changes to enable recovery of the current tape symbol through counts circumventing both barriers. Further, we empirically show that the use of such signpost tokens and value change encodings provide actionable guidance to improve length generalization on hard problems.
• Abstract（参考訳）: CoT(Chain-of-Thought)は、トランスフォーマーの性能を実証的に改善し、理論的にはチューリング完全性への表現性を高めることが示されている。 しかし、TransformerがCoTトレースへの一般化を学習できるかは、トレーニング中に見られるものよりも長い。 我々は、トランスフォーマー長の一般化に関する最近の理論フレームワークを使用し、標準的な位置エンコーディングと有限アルファベットの下では、CoTを持つトランスフォーマーは$TC^0$以上の問題を解決することができない。 しかし、問題の大きさで語彙を拡大させると、シミュレーション実行時にCoTトレース長が一定まで線形となるチューリングマシンの時間一般化可能なシミュレーションが得られる。 提案手法は,2つのコア障害を克服し,信頼性の高い長さ一般化を実現する。 それぞれのテープ位置をユニークなサインポストトークンに割り当て、両方の障壁を回避して現在のテープシンボルの復元を可能にするために、ログのみの値変更を行う。 さらに、このようなサインポストトークンと値変化エンコーディングを使用することで、ハード問題における長さ一般化を改善するための実用的なガイダンスが提供されることを実証的に示す。

関連論文リスト

• Universal Transformers for Circuit Computations: Perfect Length Generalization in Tiny Transformers [15.437559038107144]
  我々は,任意の深さや長さの問題を学習し,評価することのできる,確実に正しい変圧器パラメータ化を提案する。 提案手法は,変圧器に埋め込まれた回路モデルとしてアルゴリズムタスクを概念化し,単一の前方通過で深度1回路の低減を可能にする。
  論文  参考訳（メタデータ） (2026-08-31T16:42:11Z)
• Generalization Bounds for Transformer Channel Decoders [61.55280736553095]
  本稿では,ECCTの一般化性能を学習理論の観点から検討する。 我々の知る限りでは、この研究はこの種のデコーダに対する最初の理論的一般化保証を提供する。
  論文  参考訳（メタデータ） (2026-01-11T15:56:37Z)
• Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization [53.89723291716722]
  AI推論に関する重要な問題は、モデルが学習した推論パターンを外挿して、より長いチェーン・オブ・シークレット(CoT)で難しいタスクを解決できるかどうかである。 状態追跡問題の代数構造が、学習されたCoTの外挿の度合いをいかに支配するかを数学的に証明する。 定数深度変換器はCoTで$mathsfNC1$-complete問題を確実に学習することを保証する。
  論文  参考訳（メタデータ） (2025-11-10T18:40:24Z)
• Quantitative Bounds for Length Generalization in Transformers [58.175107357008876]
  変圧器における長さ一般化(LG)問題について検討する。 LGは、長い列上の変圧器の内部挙動が短い列上の振舞いによって「シミュレート」できるときに発生する。
  論文  参考訳（メタデータ） (2025-10-30T21:31:36Z)
• A Formal Framework for Understanding Length Generalization in Transformers [14.15513446489798]
  因果変換器における長さ一般化を解析するための厳密な理論的枠組みを導入する。 我々は,この理論を,アルゴリズムおよび形式言語タスクにおける長さ一般化の成功と失敗の予測器として実験的に検証した。
  論文  参考訳（メタデータ） (2024-10-03T01:52:01Z)
• Looped Transformers for Length Generalization [41.99378201613648]
  適応的なステップ数を持つループ変換器は長さの一般化を著しく向上することを示す。 我々は,提案した学習アルゴリズムを用いてループ変換器を訓練し,様々なタスクに対して,高度に長大な一般化可能な解を学習することを確認する。
  論文  参考訳（メタデータ） (2024-09-24T01:21:17Z)
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
  思考の連鎖(CoT)は、算術や記号的推論タスクにおいて、大きな言語モデル(LLM)の精度を向上させるための非常に効果的な方法である。 この研究は、表現性のレンズを通してデコーダのみの変換器に対するCoTのパワーを理論的に理解する。
  論文  参考訳（メタデータ） (2024-02-20T10:11:03Z)
• Transformers Can Achieve Length Generalization But Not Robustly [76.06308648699357]
  長さ一般化の成功は,データ形式や位置エンコーディングのタイプと密接に関連していることを示す。 標準変換器が入力長の2.5倍のシーケンス長に外挿できることを初めて示す。
  論文  参考訳（メタデータ） (2024-02-14T18:18:29Z)
• The Expressive Power of Transformers with Chain of Thought [29.839710738657203]
  実際には、トランスフォーマーは「思考の連鎖」や「スクラッチパッド」を使用することで改善できる。 答えはYESであるが、増加量は中間生成量に大きく依存する。 また, 線形ステップでは, コンテクストに敏感な言語に変換器デコーダを配置することが示唆された。
  論文  参考訳（メタデータ） (2023-10-11T22:35:18Z)

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

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