Barriers to Universal Reasoning With Transformers (And How to Overcome Them)

論文「Barriers to Universal Reasoning With Transformers (And How to Overcome Them)」の詳細な技術的サマリーを以下に示す。

1. 問題定義

チェーン・オブ・ thought (CoT) プロンプトは、経験的にトランスフォーマーのパフォーマンスを向上させ、理論的にはその表現力をチューリング完全性にまで高めることが示されているが、重要なギャップが残っている：トランスフォーマーは、訓練中に観測された長さよりも長い CoT 推論を一般化して学習できるか？

既存の経験的証拠は、CoT 推論の長さが増加するにつれて、アルゴリズム的および論理的タスクであってもトランスフォーマーの精度が急激に低下することを示唆している。本論文は、長さ一般化可能な学習性というより厳格な要件の下で、チューリング完全性の理論的主張が成り立つかどうかを検証する。具体的には、以下の問いを投げかける：

• 標準的な CoT 形式は、より長い系列へ一般化する際、トランスフォーマーが複雑性クラス $\text{TC}^0$（定数深さの閾値回路）を超えた問題を解決することを可能にするか？
• この一般化を妨げる具体的な構造的障壁は何か？
• これらの障壁は、特定のフォーマット戦略によって克服できるか？

2. 手法

著者は、理論的定式化と経験的検証の組み合わせを採用する：

理論的枠組み

本研究は、トランスフォーマーの長さ一般化に関する最近の理論的枠組みを利用する：

• C-RASP: 有限アルファベットと位置符号化を備えたトランスフォーマーの推論に関する定式化。所属性は長さ一般化の保証を意味する。
• C-RASP:* 無限アルファベット（具体的には、無制限のサインポストトークン）と局所一致述語を許可する C-RASP の拡張。
• 学習モデル: 著者は、増加する入力長さで訓練されたトランスフォーマーの系列が、単一の基盤アルゴリズムに収束するという理想化された学習モデルを採用する。タスクがこれらの定式化内で表現可能であれば、一般化が保証される。

経験的設定

• タスク: 3 つのアルゴリズム的推論タスクが選択された：
  1. パリティ: 2 進文字列内の 1 の数が偶数か奇数かを判定する。
  2. ブール評価: 入れ子になった論理式真理値を評価する。
  3. S5 置換: 一連の交換操作後の 5 つのオブジェクトの状態を追跡する。
• モデル:
  • ゼロから訓練 (From-Scratch): 特定のフォーマットあり・なしの CoT 推論で訓練された GPT-2 モデル（25M パラメータ）。
  • 事前学習済み LLM: Qwen2.5-7B、Mistral-Small-24B、Llama-3.3-70B に対するゼロショットおよびフューショットプロンプト実験。
• フォーマット変種:
  • Naive CoT: 標準的な逐次推論。
  • サインポストトークン: 任意のアドレス指定を可能にするため、特定の位置または操作に一意の識別子（例：<34>）を割り当てる。
  • 値変化エンコーディング: 各ステップで完全な状態をログする代わりに、モデルは値の変化（例：1 -> 0）のみをログするか、値が変更されていない場合を明示的に記録する。

3. 主要な貢献と理論的結果

貢献 1: 有限アルファベットの限界（否定的結果）

著者は、標準的な位置符号化と有限アルファベットの下では、CoT を備えたトランスフォーマーが $\text{TC}^0$ 以外の問題を解決するために長さ一般化を行うことができないことを証明する。

• 定理 3.4: 言語 $L$ の CoT 推論が C-RASP（位置プリミティブ付き）で表現可能であれば、$L$ は $\text{TC}^0$ で定義可能である。
• 含意: CoT は理論的にチューリング完全を可能にするが、語彙が固定されている場合、そのようなシミュレーションの学習性は $\text{TC}^0$ によって制限される。表現力の利点は、長さ一般化可能な学習性には転嫁されない。

貢献 2: 無限アルファベットによる障壁の克服（肯定的結果）

本論文は、長さ一般化に対する 2 つの中核的な障壁を特定する：

1. 反復コピー: 任意の文字列を新しい位置にコピーする難しさ。
2. 最終出現の検索: 複数の更新が発生した際、変数の最も最近の値を取得する難しさ（一意ではない検索）。

これらを克服するため、著者はC-RASP*を用いた構成を提案する：

• サインポストトークン: テープの各位置または操作ステップに、無限アルファベットからの一意で無制限のトークンを割り当てる。これにより、絶対的な同一性を記憶することなく任意のインデックス付けが可能となり、コピーの障壁が解決される。
• 値変化エンコーディング: 完全な状態をログする代わりに、CoT は遷移（例：「値が $x$ から $y$ に変更された」）のみをログする。現在の状態は、初期状態に対する正味の変化を数えることで回復される。これにより、検索障壁が解決され、現在の値が「最後」の出現の検索ではなく、カウントの関数となる。
• 定理 3.8: 無限アルファベットを持つサインポストトークンを利用し、値変化を通じて計算をエンコードする場合、CoT を備えたトランスフォーマーは任意のチューリングマシンをシミュレートするために長さ一般化を行うことができる。CoT 推論の長さは、シミュレートされた実行時間に対して線形のままとなる。

4. 経験的結果

ゼロから訓練 (From-Scratch Training)

• パリティ: 標準的な CoT は訓練長さを超えて一般化できなかった。値変化エンコーディングは、訓練長さの 2 倍への堅牢な一般化を可能にした。
• ブール評価および S5 置換: これらのより困難なタスク（$\text{TC}^0$ 外）は、Naive CoT では失敗した。サインポストトークンの追加は長さ一般化を大幅に改善したが、モデルが利用可能な「ショートカット」（ヒューリスティック）のため、S5 は依然として困難であった。
• 2 進置換: 高い反復性を持つ S5 の変種。Naive およびサインポストのみの CoT は、「一意ではない検索」エラーにより失敗した。サインポスト＋値変化の組み合わせが最良の結果をもたらし、両方のメカニズムの理論的必要性を確認した。

事前学習済み LLM へのプロンプト

• サインポスト: フューショットプロンプトで自然数をサインポストの手がかりとして使用すると、すべてのテストされた LLM（7B から 70B）において、特に長い系列長でブールおよび S5 タスクのパフォーマンスが向上した。
• 値変化: 変数割り当てを追跡するコード実行タスクにおいて、値の変化を明示的にログするインラインコメント（例：# node a: 9 -> 0）を提供することは、中間推論ステップがなくても、標準的なコードフォーマットと比較して最終回答の精度を大幅に向上させた。

5. 意義と結論

• CoT 成功の再定義: 本論文は、CoT の成功は「思考」プロセスそのものにあるのではなく、推論のフォーマットに大きく依存すると主張する。標準的な CoT 形式は、学習性に必要な制約（局所性と翻訳不変性）に違反するため、一般化に失敗することが多い。
• 理論的境界: トランスフォーマーのチューリング完全性は条件付きであることを明確にする。これは表現力（解決策のハードコーディング）に対しては成り立つが、特定の構造的支援（無限アルファベット/サインポスト）が提供されない限り、学習性（一般化するモデルの訓練）に対しては成り立たない。
• 実践的ガイドライン: 発見は、困難な推論タスクにおける LLM のパフォーマンスを向上させるための実行可能な原則を提供する：
  1. インデックスヒントの使用: 検索を支援するため、位置またはステップに一意の識別子を明示的にマークする。
  2. 状態ではなく変化をログする: 検索の曖昧さを避けるため、完全な状態ダンプではなく、状態遷移を強調する推論推論をフォーマットする。
• 将来の方向性: この研究は、将来の事前学習データおよび CoT 方式は、これらの理論的制約を念頭に置いて設計されるべきであり、それによって長期的推論タスクにおけるトランスフォーマーの計算能力の全開花が可能になると示唆している。

要約すると、本論文は、トランスフォーマーが理論的には普遍的推論が可能である一方、これを長さ一般化可能な形で実現するには、サインポストトークンと値変化エンコーディングの使用を通じて、特定のアーキテクチャおよびフォーマットの障壁を克服する必要があることを実証している。