On the Computational Complexity of Structural 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 NC^1 against the learnable ceiling 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 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 TC^0. Under the standard assumption TC^0 neq 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.

Source: arXiv cs.CL | 2026-07-23