Recurrent Reasoning on Symbolic Puzzles with Sequence Models

技術要約：シーケンスモデルによる記号的パズルへの回帰的推論

問題提起
大規模言語モデル（LLM）は、記号的およびアルゴリズム的なタスクにおいて、一見すると習熟しているように見えることが多い。しかし、このパフォーマンスは、問題の長さや難易度が増したり、訓練分布からわずかに逸脱したりすると、脆い挙動を隠蔽していることが頻繁に露呈する。現在の推論ベンチマークは、妥当な最終回答の生成を優先しがちであり、解決プロセスの堅牢性、最小性、および安定性を軽視している。本論文は、アルゴリズム的問題においては、単に妥当な終止点を得るだけでなく、有効な中間アクションを繰り返し選択し、不正な遷移を回避し、長いホライゾンにわたって一貫性を維持する能力こそが正当性の要件であると主張する。著者らは、アルゴリズム的推論が、真の堅牢性と浅薄なパターンマッチングを区別するための重要な設定であると断じている。

手法：RecurrReason ベンチマーク
これらの限界に対処するため、著者らは4つの回帰的論理パズルで構成される、難易度制御型のベンチマーク RecurrReason を導入する：

1. ブロック・ワールド (Block World): スタック内のブロックの並べ替え。
2. チェッカーのジャンプ (Checkers Jumping): 直線状の盤面上で赤と青のチェッカーの位置を入れ替える。
3. ハノイの塔 (Tower of Hanoi): サイズ制約の下でディスクをペグ間で移動させる。
4. 川渡り (River Crossing): 安全制約を守りながら、アクターとエージェントのペアを川の対岸へ輸送する。

このベンチマークは以下の特性に基づいて構築されている：

• スケーラブルな難易度: 各パズルは、$N \in \{1, \dots, 10\}$ の単一の整数によってパラメータ化されている。
• 最適軌跡: すべてのインスタンスは、最適な軌跡を生成するために幅優先探索（BFS）を用いて解かれており、合計で10,817個の一意なパズルと285,933個の動きが含まれる。
• タスク定式化: タスクは「次の一手の予測」問題としてフレーム化される。モデルは現在の状態 ($s_t$) と目標状態 ($g$) を受け取り、次の状態 ($s_{t+1}$) を予測しなければならない。評価は、正解の中間状態を用いない自己回帰的なロールアウトによって行われる。
• 評価プロトコル: モデルは $N=1$ から $7$ のインスタンスで訓練され、保持されたイン分布（in-distribution）のインスタンス（$N=1$ から $7$）およびアウトオブ分布（OOD）のインスタンス（$N=8$ から $10$）で評価される。指標には、軌跡の成功率、動きの合法性、および最適性ギャップが含まれる。

実験設定
本研究では、一貫したデータ分割と訓練条件（スクラッチ、ゼロショット、およびファインチューニング）の下で、2つのTransformerファミリーをベンチマークする：

1. T5型 (Encoder-Decoder): 60Mパラメータのモデル（T5-small）。エンコーダは、連結された状態と目標に対して双方向のアテンションを計算し、目標をあらゆるステップにおける「第一級の」条件付け信号とする。
2. GPT-2型 (Decoder-Only): 124Mパラメータのモデル（GPT-2）を使用。因果的マスク（causal mask）を用いることで、現在の状態のトークンが（後続に現れる）目標トークンにアテンションを向けることを防ぎ、目標指向のプランニングに対する構造的なボトルネックを生じさせる。

主要な結果
実験により、パズルの構造がモデルの規模や事前学習よりも、学習可能性の強力な決定要因であることが明らかになった：

• ブロック・ワールドの成功: ファインチューニングされた事前学習済みT5モデルは、検証精度97.27%、OOD精度81.00%を達成した。この成功は、パズルの局所的な遷移関数（スタックの最上部のみをチェックする $O(1)$ の複雑性）、線形な解の長さの成長 ($L(N) = O(N)$)、および密な訓練信号に起因する。
• その他のパズルにおける失敗:
  • 川渡り: すべての条件下で全モデルが0.00%を記録した。このパズルは、毎ステップでのグローバルな制約検証 ($O(N)$) を必要とし、組み合わせ的なアクション空間を持つため、すべてのアーキテクチャを打ち負かした。
  • ハノイの塔: モデルは最大でも11.11%の検証精度（自明な $N=1$ のケースのみ）に留まり、OODでは0.00%であった。指数関数的な解の長さ ($2^N - 1$) が誤差の蓄積を引き起こし、$N=1$ を超える汎化を妨げている。
  • チェッカーのジャンプ: モデルは最大1.11%の検証精度を達成したが、これは開始状態と目標状態が等しい自明なインスタンスのみを解いたものである。二次的な解の長さとデッドエンドを回避する必要性が、克服不可能な障壁となった。
• アーキテクチャ vs 規模: 小規模なT5モデル（60M）は、より大規模なGPT-2モデル（124M）を大幅に上回る性能を示した。著者らは、これをエンコーダ・デコーダ・アーキテクチャが目標に対して双方向のアテンションを向ける能力を持つのに対し、デコーダのみのモデルにおける因果的マスクが、プランニングのための構造的なボトルネックを生み出しているためであるとしている。
• 事前学習の転移: 事前学習の恩恵は、局所的に構造化された遷移関数を持つパズル（ブロック・ワールド）においてのみ観察された。グローバルな制約を必要とするパズル（川渡り）や再帰的な分解を必要とするパズル（ハノイの塔）への転移は見られなかった。

失敗モード分析
著者らは、パズルの構造と相関する特定の失敗モードを特定している：

• 無効な動き (Invalid Moves): グローバルな制約を持つパズル（ハノイの塔、川渡り）における失敗の主因であり、制約の汎化失敗を示している。
• ループ (Loops): デコーダのみのモデルにおけるブロック・ワールドの主な失敗モードであり、目標指向の選択を伴わない部分的なルールの学習を示唆している。
• 早期停止 (Premature Stops): ハノイの塔におけるGPT-2で観察され、訓練データにおけるストップトークンの統計的な過剰表現に関連している。

意義と主張
本論文は、アーキテクチャの帰納バイアスが規模よりも重要であると主張している。具体的には以下の通りである：

1. 構造的決定論: パズルの学習可能性は、3つの構造的特性（遷移の局所性、アクション空間のサイズ、および解の長さの成長）によって決定される。著者らは、成功確率が解の長さに伴って指数関数的に減少することを示す誤差蓄積モデル（$P \approx e^{-\epsilon L(N)}$）を定式化している。
2. 目標条件付け: 双方向の目標条件付け（T5に見られるもの）は目標指向のプランニングに不可欠であるが、因果的アテンション（GPT-2に見られるもの）は、より大きなパラメータ数を持っていても効果的なプランニングを妨げる構造的ボトルネックを生み出す。
3. 事前学習の限界: 事前学習は階層的な帰納バイアスを付与するが、それは局所的に分解可能な構造を持つタスクにのみ転移する。グローバルな制約や再帰的な深さを扱う能力を本質的に備えるものではない。
4. 今後の方向性: これらの結果は、LLMにおける信頼性の高いマルチステップ推論には、単なるモデルサイズの拡大ではなく、アーキテクチャ探索能力または明示的な記号的制約チェックが必要であることを示唆している。

著者らは、RecurrReasonが、長さの汎化、目標条件付きプランニング、および系統的なアルゴリズム的推論のためのアーキテクチャ的要件に関する将来の研究のための、制御されたテストベッドを提供すると結論づけている。