Почему чистые Transformer не способны выучить структурную генерализацию: доказательство

Researchers published a paper on arXiv in July 2026 that mathematically proves: a pure Transformer is incapable of autonomously learning structural generalization from finite data. The reason is a gap between the computational complexity of the task itself (class NC¹) and the proven learnability ceiling of transformers (class TC⁰).

What was actually proven

The authors gave, for the first time, a formal definition of structural generalization — a model's ability to assemble meaning from familiar parts in unfamiliar combinations. Before this work, the concept was measured by a dozen benchmarks, but had never been rigorously defined. The definition translates two intuitive premises — compositional structure and unbounded generalization — into the language of mathematics.

The key move is to show that the task requires the computational power of class NC¹, whereas a pure Transformer, per the proof by Krause et al. (2026), is limited to class TC⁰. Under the standard complexity-theory assumption TC⁰≠NC¹, the conclusion is rigorous: the required capability lies above the architecture's ceiling.

• NC¹ — the computational lower bound of the structural generalization task
• TC⁰ — the proven learnable ceiling of pure transformers (Krause et al., 2026)
• Tree evaluation (BFVP) is NC¹-complete — proven by Buss back in 1987
• Under the standard assumption TC⁰≠NC¹, the gap is insurmountable
• Neurosymbolic systems bypass the hard part by hand-wiring semantics (G_γ)

Where exactly the Transformer hits a wall

Every compositional rule breaks down into two projections: a syntactic one (F_γ) and a semantic one (G_γ) — this is how the Montagovian model of meaning (after Richard Montague), which the authors rely on, is structured. This separation makes it possible to pinpoint exactly which half of the task is genuinely hard.

Semantic tree evaluation (the G_γ side) is a special case of the BFVP problem, which, according to Buss (1987), is NC¹-complete. A pure Transformer is forced to learn both sides at once, but its learnable class does not extend beyond TC⁰. The gap between TC⁰ and NC¹ is exactly the wall that autonomous learning breaks against — no matter how much data the model sees.

Why benchmarks are misleading

Neurosymbolic systems score better on structural generalization benchmarks precisely because their semantic projection (G_γ) is hand-wired rather than learned. They bypass the genuinely hard half of the task and get a high score by going around the NC¹-complete core.

Hence the paper's main conclusion: a benchmark score does not distinguish what was learned from what was given in advance. The test of "can the model 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 genuine compositional generalization, no matter how much data they are given. For practitioners, this is an argument in favor of hybrid, neurosymbolic approaches; for researchers, it's a reason to read high benchmark scores more cautiously.

Frequently Asked Questions

What is structural generalization?

It is a model's ability to correctly process new combinations of familiar elements — for example, understanding a phrase made of known words in a structure that did not appear during training. The paper's authors were the first to give it a formal mathematical definition.

Does this mean transformers are useless?

No. The proof concerns a "pure" transformer and a 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 outperform transformers on these benchmarks?

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