New Proof: Pure Transformers Cannot Learn Structural Generalization

Zichao Wei's paper, 'On the Computational Complexity of Structural Generalization,' formally defines structural generalization for the first time, translating compositional structure and unbounded generalization into mathematical language. The definition itself is neutral—even a hard-coded compiler satisfies it—but the scientific question is whether this capacity can autonomously emerge from finite data. Under a Montagovian instantiation, compositional rules split into syntactic (Fγ) and semantic (Gγ) faces. Tree evaluation on the Gγ side is an instance of the Boolean Formula Value Problem (BFVP), which is NC¹-complete (proved by Buss, 1987). A pure Transformer must learn both faces simultaneously, but Kraus et al. (2026) showed its learnable class is a subset of TC⁰. Under the standard complexity theory assumption TC⁰ ≠ NC¹, a pure Transformer cannot learn structural generalization.

Neuro-symbolic systems achieve top benchmark scores precisely because they inject the Gγ component directly, sidestepping the genuinely hard computational problem. This means current benchmarks fail to distinguish between learned and given structural capacity, making reported scores misleading. The paper clarifies the computational boundary: any system that claims to learn structural generalization must prove it can solve NC¹-hard problems within the neural architecture alone. For the AI industry, this result implies that purely end-to-end neural models (like Transformers) may need architectural enhancements or explicit symbolic components to achieve true compositional generalization. The finding has direct implications for benchmarks used to evaluate language models, suggesting they should be redesigned to measure emergent vs. engineered structural reasoning.