On the Computational Complexity of Structural Generalization

A new arXiv paper (2607.19573v1) formally defines structural generalization and proves that pure Transformers cannot learn it under the standard complexity assumption TC⁰ ≠ NC¹. The authors show that neuro-symbolic systems achieve high benchmark scores by injecting the semantic face Gγ, which is NC¹-complete, rather than learning it from data. The paper argues that benchmark scores conflate learned capacity with given structure, undermining claims of emergent generalization.

arXiv:2607.19573v1 Announce Type: new Abstract: 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 \gamma$ and a semantic face $G \gamma$ . Tree evaluation on the $G \gamma$ 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 \gamma$, sidestepping the genuinely hard half. Benchmark scores cannot distinguish "learned" from "given." This is what this paper sets out to make clear.