# On the Computational Complexity of Structural Generalization

arXiv: https://arxiv.org/abs/2607.19573 · HTML: https://mlsanity.com/paper/2607.19573/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 24 references that are in the map.
- First posted on arXiv 21 Jul 2026.

## Builds on (most cited first, 11 of 11)

- [Compositionality decomposed: how do neural networks generalise?](https://mlsanity.com/paper/1908.08351/) (2019)
- [COGS: A Compositional Generalization Challenge Based on Semantic Interpretation](https://mlsanity.com/paper/2010.05465/) (2020)
- [The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://mlsanity.com/paper/2207.00729/) (2022)
- [On the Turing Completeness of Modern Neural Network Architectures](https://mlsanity.com/paper/1901.03429/) (2019)
- [Why are Sensitive Functions Hard for Transformers?](https://mlsanity.com/paper/2402.09963/) (2024)
- [Structural generalization is hard for sequence-to-sequence models](https://mlsanity.com/paper/2210.13050/) (2022)
- [SLOG: A Structural Generalization Benchmark for Semantic Parsing](https://mlsanity.com/paper/2310.15040/) (2023)
- [AMR Dependency Parsing with a Typed Semantic Algebra](https://mlsanity.com/paper/1805.11465/) (2018)
- [Compositional Reasoning with Transformers, RNNs, and Chain of Thought](https://mlsanity.com/paper/2503.01544/) (2025)
- [Strengthening Structural Inductive Biases by Pre-training to Perform Syntactic Transformations](https://mlsanity.com/paper/2407.04543/) (2024)
- [Barriers to Universal Reasoning With Transformers (And How to Overcome Them)](https://mlsanity.com/paper/2604.25800/) (2026)

## Abstract (arXiv)

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.