論文の概要: 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（参考訳）: トランスフォーマーと共謀するバリアたち(そして克服する方法)
• Authors: Oliver Kraus, Yash Sarrof, Yuekun Yao, Alexander Koller, Michael Hahn,
• 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つのコア障害を克服し,信頼性の高い長さ一般化を実現する。 それぞれのテープ位置をユニークなサインポストトークンに割り当て、両方の障壁を回避して現在のテープシンボルの復元を可能にするために、ログのみの値変更を行う。 さらに、このようなサインポストトークンと値変化エンコーディングを使用することで、ハード問題における長さ一般化を改善するための実用的なガイダンスが提供されることを実証的に示す。

関連論文リスト

• Generalization Bounds for Transformer Channel Decoders [61.55280736553095]
  本稿では,ECCTの一般化性能を学習理論の観点から検討する。 我々の知る限りでは、この研究はこの種のデコーダに対する最初の理論的一般化保証を提供する。
  論文  参考訳（メタデータ） (2026-01-11T15:56:37Z)
• Quantitative Bounds for Length Generalization in Transformers [58.175107357008876]
  変圧器における長さ一般化(LG)問題について検討する。 LGは、長い列上の変圧器の内部挙動が短い列上の振舞いによって「シミュレート」できるときに発生する。
  論文  参考訳（メタデータ） (2025-10-30T21:31:36Z)
• 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)

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

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