LLMはグラフ上の最短経路を学習できる——しかしタスクの視野が延びると失敗する

何がテストされましたか？

研究者のTong、Ye、Borovykh、Shokri氏らはarXivで論文を発表し、LLMが古典的なアルゴリズム問題——グラフ内の最短経路探索——において系統的汎化を達成できるかどうかを体系的に分析しました。テストは汎化の2つの独立した次元をカバーしました：

1. 空間的転移 — あるグラフセットで学習したモデルは、異なるトポロジーを持つ未見のマップ上の問題を解けるか？
2. 視野長によるスケーリング — 短いパス（例えば5-10ステップ）で学習したモデルは、より長いパス（50ステップ以上）を正しく解けるか？

この方法論は標準的なベンチマークタイプよりも意図的に広範です——問題が新しいかどうかだけでなく、要求がモデルが訓練で見たものよりも構造的に要求が高いかどうかも測定します。

何が発見されましたか？

結果は一貫しており、注目に値します：

• 空間的転移： 成功。あるグラフセットでパス探索を学んだモデルは、同じサイズの未見のトポロジーに汎化することに成功します。これは「アルゴリズムを学ぶ」ことがある程度可能であることを意味します。

• 長さスケーリング： 一貫した失敗。パスの長さが訓練範囲を超えると、モデルは再帰的不安定性のために失敗します——あるステップでの小さなエラーが最後まで指数関数的に蓄積します。

3つの介入も追加でテストされました：

• データカバレッジが能力の境界を定義する — モデルは訓練で見たことを知っており、それを超えたスケーリングは機能しません。
• RL（強化学習）は訓練範囲内での安定性を改善するが、汎化の境界を拡張しません。
• 推論時のスケーリング（トークン予算の増加、思考の連鎖）は役立ちますが、基本的な長さスケーリング問題を解決しません。

なぜこれが自律的エージェントにとって重要なのですか？

多くの実際のエージェントタスクは長い視野を必要とします：マルチステッププランニング、研究、数日にわたるソフトウェアエンジニアリングプロジェクト、複雑なシステムの反復的なデバッグ。LLMが長さで構造的にスケールできない場合——この論文が示唆するように——エージェントの自律性は訓練で見たことがある問題のサイズによって根本的に制限されます。

これは以前の発見と一致しています（例えばLongCoTベンチマーク、GPTが長い思考の連鎖推論で9.8%を達成）：表面上最も強力なモデルは問題が延びると崩壊します。

実践的にはどういう意味ですか？

研究者は問題が解決不可能だとは主張していませんが、3つの避けられない真実を特定しています：

1. 合成データセットカバレッジは明示的に長いパスを含む必要があります——そうでなければモデルはそれらの処理方法を決して知りません。
2. RLと推論時スケーリングは魔法の杖ではありません — モデルがすでに学んだことを改善しますが、新しい系統的能力は追加されません。
3. アーキテクチャの変更（階層的エージェント、明示的な状態管理を伴うプランニング）が真の長さ汎化には必要かもしれません。

AIニュース読者へのまとめ：次回モデルが「自律的な研究プロジェクトを行う」と読んだとき、その視野が実際にどれほど深いか、そして問題がそのモデルの訓練範囲内か外かを問うことが重要です。