论结构泛化的计算复杂度

一篇新论文《论结构泛化的计算复杂度》为人工智能中一个长期存在的概念——结构泛化（structural generalization）提供了首个正式定义，并从计算复杂性角度揭示了纯Transformer架构的根本局限性。该研究由Zichao Wei完成，首次将结构泛化的两个核心前提——组合结构与无限泛化——转化为精确的数学语言。定义本身是中性的：即便是硬编码规则的编译器也能满足。但结构泛化成为一个科学问题的关键在于，这种能力能否从有限数据中自主涌现。

论文的核心发现涉及计算复杂性类NC1与TC0的对决。在蒙塔古语义框架下，每个组合规则被拆分为两个投影：句法面（Fγ）和语义面（Gγ）。Gγ侧的树求值等价于布尔公式值的并行计算（BFVP），这是一个NC1完全问题（Buss, 1987）。而纯Transformer的可学习类别被证明包含于TC0（Kraus等人，2026）。在标准假设TC0 ≠ NC1下，纯Transformer无法学习结构泛化。

论文进一步指出，神经符号系统之所以在基准测试中表现最佳，正是因为它们注入了Gγ投影，绕过了真正困难的部分。因此，基准测试分数无法区分“学习”与“预设”。这一发现具有重要影响：当前的评测方法可能高估了神经符号系统的学习能力，而低估了纯Transformer的局限性。该研究旨在澄清这一根本性混淆，并为未来研究提供坚实的理论基础。

总而言之，这篇论文不仅为结构泛化建立了严格的数学框架，还通过计算复杂性理论揭示了不同架构的能力边界，对人工智能领域的评测方法和架构设计具有深远意义。