Structural generalization — the ability to compose known elements into unseen combinations — has long been the favored testing ground for language model reasoning. Yet a formal definition was missing. A new theoretical contribution fills this gap with a neutral mathematical formulation: it is satisfied just as well by a compiler that hard-codes the rules as by a system that learns them from data. The point, the authors argue, is that the scientific question becomes interesting only when the capacity must emerge autonomously from finite examples.

And that is where computational complexity draws a sharp line. The problem of structural generalization, when split into a syntactic and a semantic projection (in Montagovian style), requires evaluating semantic composition trees. That task is an instance of BFVP, notoriously NC¹-complete — a class capturing parallelizable yet inherently recursive operations, like parsing nested expressions. Pure Transformers, on the other hand, belong to the weaker class TC⁰: they can compute functions via constant-depth threshold circuits but cannot simulate the recursion needed for arbitrarily nested structures. The proof by Kraus et al. (2026) encapsulates this limit: what a Transformer can learn from data is contained in TC⁰. Under the standard assumption that TC⁰ is strictly weaker than NC¹, a pure Transformer can never learn full structural generalization.

This is no theoretical footnote. Those deploying LLMs for tasks demanding compositional inference — layered database queries, contract clause analysis, code generation with nested constraints — encounter brittle behaviors that synthetic benchmarks often miss. The reason is twofold. On one hand, standard evaluation fails to separate genuinely learned capacity from capacity “donated” by architecture or by training on undemanding distributions. On the other hand, the TC⁰ wall implies that scaling parameters and data is not enough: lexical coverage or fluency may improve, but the systematic compositionality gap remains.

The escape route indicated by the research has a precise name: neuro-symbolic systems. Models that dominate compositional generalization benchmarks explicitly inject the semantic component Gγ — for instance via symbolic parsing modules or structured memory — thereby bypassing the computational bottleneck. In practice, compositional reasoning is not learned by the Transformer but delegated to an external component operating outside the TC⁰ regime.

For those evaluating on-premise deployment of LLMs, this conclusion carries an immediate architectural reflection. An entirely Transformer-based stack, however optimized with quantization and efficient serving, will remain blind to deep compositionality unless enriched with explicit symbolic modules. Direct control over infrastructure — typical of self-hosted setups — then becomes an enabler: it allows orchestrating hybrid pipelines without relying on cloud APIs that offer little room to intervene on the model’s internal architecture. In sectors where logical correctness is non-negotiable, such as regulatory compliance or industrial diagnostics, the ability to couple a symbolic engine with an LLM is not an academic luxury but a system requirement.

The structural message, in short, is that the brute scalability of Transformers cannot replace computational expressiveness. The paper signals that the next frontier is not just building larger models, but integrating computational circuits that escape the TC⁰ perimeter — exactly what neuro-symbolic systems are already doing, often quietly, in contexts where exact answers matter.