证明纯Transformer无法学习结构化泛化，因能力上限低于理论下限。
On the Computational Complexity of Structural Generalization
- 用数学定义结构泛化：组合结构与无限泛化并列
- 纯Transformer学习能力上限为TC⁰，而结构泛化需NC¹，两者不等
- 神经符号系统靠预设语义面取胜，而非真正学习
结构泛化虽被多个基准反复衡量，却从未被正式定义。本文将其两个前提——组合结构与无界泛化——转化为数学语言。该定义本身中立：硬编码规则的编译器也满足。但只有当能力能从有限数据自主涌现时，结构泛化才成为科学问题。此问题将计算下界NC¹与纯Transformer的可学习上界TC⁰对立。在蒙塔古设定下，每个组合规则分解为句法面（Fγ）与语义面（Gγ）。对Gγ侧的树评估是BFVP的实例，属于NC¹-完全（Buss, 1987）。纯Transformer必须同时学习两面，但Kraus等（2026）证明其可学习类⊆TC⁰。在标准假设TC⁰≠NC¹下，纯Transformer无法学习结构泛化。神经符号系统得分最高，正因其注入Gγ，绕过真正困难的部分。基准分数无法区分‘学习’与‘给定’。本文旨在澄清此点。
原文摘要 · Abstract (English)
Structural generalization has been measured repeatedly by several benchmarks, yet it has never been formally defined. We give a definition that translates the two premises (compositional structure and unbounded generalization) into mathematical language. The definition itself is neutral: a compiler that hard-codes the rules satisfies it just as well. But structural generalization becomes a scientific question only insofar as the capacity can autonomously emerge from finite data. This question pits the computational lower bound $\mathrm{NC}^1$ against the learnable ceiling $\mathrm{TC}^0$ of pure Transformers. Under a Montagovian instantiation, each compositional rule splits into two projections: a syntactic face ($F_γ$) and a semantic face ($G_γ$). Tree evaluation on the $G_γ$ side is an instantiation of BFVP, which is $\mathrm{NC}^1$-complete (Buss, 1987). A pure Transformer must learn both faces at once, but Kraus et al. (2026) prove that its learnable class $\subseteq \mathrm{TC}^0$. Under the standard assumption $\mathrm{TC}^0 \neq \mathrm{NC}^1$, a pure Transformer cannot learn structural generalization. Neuro-symbolic systems achieve the best benchmark scores precisely because they inject $G_γ$, sidestepping the genuinely hard half. Benchmark scores cannot distinguish "learned" from "given." This is what this paper sets out to make clear.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。