Search papers, labs, and topics across Lattice.
This paper formalizes the concept of structural generalization by defining it mathematically, linking compositional structure and unbounded generalization to computational complexity classes. It reveals that while pure Transformers are limited to the learnable class $\mathrm{TC}^0$, they cannot achieve structural generalization due to the computational lower bound $\mathrm{NC}^1$. In contrast, neuro-symbolic systems excel in benchmarks by integrating semantic components, thus bypassing the inherent limitations faced by pure Transformers.
Structural generalization is mathematically unattainable for pure Transformers, revealing a critical limitation in their learning capabilities compared to neuro-symbolic systems.
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.
