Why Pure Transformers Can't Learn Structural Generalization: A Proof

In July 2026, researchers published a paper on arXiv that mathematically proves a pure Transformer cannot autonomously learn structural generalization from finite data. The cause is a gap between the computational complexity of the task itself (class NC¹) and the proven learnability ceiling of Transformers (class TC⁰).

What exactly was proven

The authors give the first formal definition of structural generalization: a model's ability to assemble meaning from familiar parts in unfamiliar combinations. Before this paper, the concept was measured with a dozen benchmarks but never rigorously defined. The definition translates two intuitive premises, compositional structure and unbounded generalization, into the language of mathematics.

The key step is showing that the task requires computational power of class NC¹, whereas a pure Transformer is limited to class TC⁰, as proven by Kraus et al. (2026). Under the standard complexity-theory assumption that TC⁰ ≠ NC¹, the conclusion is strict: the required capability sits above the architecture's ceiling.

• NC¹ is the computational lower bound for the structural generalization task
• TC⁰ is the proven learnability ceiling of pure Transformers (Kraus et al., 2026)
• Tree evaluation (BFVP) is NC¹-complete, as Buss proved back in 1987
• Under the standard assumption TC⁰ ≠ NC¹, the gap cannot be closed
• Neurosymbolic systems sidestep the hard part by building the semantics (G_γ) in by hand

Where exactly the Transformer hits its limit

Every compositional rule splits into two projections: a syntactic one (F_γ) and a semantic one (G_γ). This is the structure of Montague's model of meaning (after Richard Montague), on which the authors build. The split makes it possible to pinpoint which half of the task is actually hard.

Evaluating the semantic tree (the G_γ side) is a special case of the BFVP problem, which Buss (1987) showed to be NC¹-complete. A pure Transformer has to learn both sides at once, but its learnable class does not extend beyond TC⁰. The gap between TC⁰ and NC¹ is the wall that autonomous learning runs into, no matter how much data the model sees.

Why benchmarks are misleading

Neurosymbolic systems post the best scores on structural generalization benchmarks precisely because the semantic projection (G_γ) is built into them by hand rather than learned. They bypass the genuinely hard half of the task and get a high result without ever touching the NC¹-complete core.

Hence the paper's main conclusion: a benchmark score cannot distinguish what was learned from what was given in advance. Testing whether a model can generalize stops being valid if part of the mechanism was simply written in by hand.

"Benchmark scores cannot distinguish 'learned' from 'given'" — from

the paper's abstract on arXiv.

What this means

The paper draws a hard boundary: without symbolic components or architectures more powerful than TC⁰, pure Transformers will not learn true compositional generalization, no matter how much data they get. For practitioners, this is an argument for hybrid, neurosymbolic approaches. For researchers, it is a reason to read high benchmark scores more cautiously.

Frequently asked questions

What is structural generalization?

It is a model's ability to correctly handle new combinations of familiar elements, for example, to understand a sentence made of known words in a structure that never appeared in training. The authors of the paper give it a formal mathematical definition for the first time.

Does this mean Transformers are useless?

No. The proof concerns a "pure" Transformer and one specific capability: autonomously learning structural generalization from finite data. In practice, models are supplemented with symbolic components that cover the hard part of the task.

Why do neurosymbolic systems beat

Transformers on these benchmarks?

Because their semantic projection (G_γ) is specified by hand rather than learned. They skip the NC¹-complete part of the task, so a high score does not prove that the capability was actually learned.