論結構泛化的計算複雜度

一篇新論文《論結構泛化的計算複雜度》為人工智慧中一個長期存在的概念——結構泛化（structural generalization）提供了首個正式定義，並從計算複雜性角度揭示了純Transformer架構的根本侷限性。該研究由Zichao Wei完成，首次將結構泛化的兩個核心前提——組合結構與無限泛化——轉化為精確的數學語言。定義本身是中性的：即便是硬編碼規則的編譯器也能滿足。但結構泛化成為一個科學問題的關鍵在於，這種能力能否從有限資料中自主湧現。

論文的核心發現涉及計算複雜性類NC1與TC0的對決。在蒙塔古語義框架下，每個組合規則被拆分為兩個投影：句法面（Fγ）和語義面（Gγ）。Gγ側的樹求值等價於布林公式值的平行計算（BFVP），這是一個NC1完全問題（Buss, 1987）。而純Transformer的可學習類別被證明包含於TC0（Kraus等人，2026）。在標準假設TC0 ≠ NC1下，純Transformer無法學習結構泛化。

論文進一步指出，神經符號系統之所以在基準測試中表現最佳，正是因為它們注入了Gγ投影，繞過了真正困難的部分。因此，基準測試分數無法區分“學習”與“預設”。這一發現具有重要影響：當前的評測方法可能高估了神經符號系統的學習能力，而低估了純Transformer的侷限性。該研究旨在澄清這一根本性混淆，併為未來研究提供堅實的理論基礎。

總而言之，這篇論文不僅為結構泛化建立了嚴格的數學框架，還透過計算複雜性理論揭示了不同架構的能力邊界，對人工智慧領域的評測方法和架構設計具有深遠意義。