この記事では、トランスフォーマーがグラフの連結性に関する問題に対して一般的なアルゴリズムを学習できず、脆弱なヒューリスティックに依存してしまう現象について理論的および実証的に説明しています。著者らは簡略化されたトランスフォーマーアーキテクチャである分離トランスフォーマーを考察し、L層のモデルが直径が最大3^Lのグラフに対して解決能力を持つことを証明しました。主要な発見は、訓練データがモデルの能力内にあるかどうかが学習戦略に影響を与えることです。モデルの能力内のグラフでは適切なアルゴリズム解が学習されるのに対し、能力を超えたグラフではノードの次数に基づいたシンプルなヒューリスティックが学習されます。最終的に、モデルの能力内に訓練データを制限することで、正確なアルゴリズムが学習できることを実証しています。