構造的一般化の計算複雑性について

新しい論文「構造的一般化の計算複雑性について」は、人工知能における長年の概念である構造的一般化に初めて形式的な定義を与え、純粋なTransformerアーキテクチャの根本的な限界を計算複雑性の観点から明らかにしました。この研究はZichao Weiによって行われ、構造的一般化の2つの中核的前提——構成構造と非有界一般化——を正確な数学言語に変換しました。定義自体は中立的で、ルールをハードコードするコンパイラでも満たせます。しかし、その能力が有限データから自律的に出現できるかどうかが科学問題となります。

論文の核心は計算複雑性クラスNC1とTC0の対決です。モンタギュー意味論の枠組みでは、各構成ルールは2つの投影、すなわち構文面（Fγ）と意味面（Gγ）に分割されます。Gγ側の木評価はブール値の並列計算（BFVP）のインスタンスであり、これはNC1完全問題です（Buss, 1987）。一方、純粋なTransformerの学習可能なクラスはTC0に含まれることが証明されています（Krausら, 2026）。標準的な仮定TC0 ≠ NC1の下では、純粋なTransformerは構造的一般化を学習できません。

論文は、ニューロシンボリックシステムがベンチマークで最高スコアを達成するのは、まさにGγを注入することで真に困難な半分を回避しているからだと指摘します。ベンチマークスコアは「学習された」ものと「与えられた」ものを区別できません。この発見は重要な影響を持ちます：現在の評価手法はニューロシンボリックシステムの学習能力を過大評価し、純粋なTransformerの限界を過小評価している可能性があります。この研究は、その根本的な混乱を明確にすることを目的としており、将来の研究に強固な理論的基盤を提供します。

要約すると、この論文は構造的一般化に厳密な数学的枠組みを確立しただけでなく、計算複雑性理論を通じて異なるアーキテクチャの能力境界を明らかにし、人工知能の評価手法とアーキテクチャ設計に深遠な意味を持ちます。