On the Computational Complexity of Structural Generalization

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 NC1 against the learnable ceiling TC0 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 NC1-complete (Buss, 1987). A pure Transformer must learn both faces at once, but Kraus et al. (2026) prove that its learnable class subseteq TC0. Under the standard assumption TC0 neq NC1, 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.