Compositional generalization — the ability to understand novel combinations of familiar parts — is one of the most persistent failures of neural networks. Models that learn “red circle” and “blue square” cannot reliably generalize to “red square” without explicit training. The failure is well-documented but poorly understood at the structural level.
arXiv:2603.16123 proves that compositional generalization is equivalent to functoriality of the decoder. A decoder generalizes compositionally if and only if it preserves the compositional structure of the input — mapping composed inputs to composed outputs in a structure-preserving way. This is precisely what a functor does in category theory.
The proof has a sharp negative consequence: softmax self-attention is not functorial for any non-trivial compositional task. The attention mechanism, by design, mixes all positions with data-dependent weights. This mixing violates the structure-preservation that functoriality requires. Attention can learn to approximate compositional behavior on trained examples, but it cannot guarantee it on novel compositions. The failure to generalize compositionally is architectural, not a matter of insufficient training data.
The positive consequence: decoders built by structural concatenation — assembling outputs from parts using the same operations used to assemble inputs — are strict monoidal functors. They are compositional by construction. In practice, these architectures achieve 2-10x error reduction on compositional tasks compared to attention-based alternatives.
The category-theoretic equivalence transforms a vague ML desideratum (“the model should generalize compositionally”) into a precise mathematical condition (“the decoder must be a functor”). The condition is checkable: given an architecture, you can determine mathematically whether it is capable of compositional generalization before training it. The impossibility result for attention and the constructive result for concatenation follow from the same theorem.
Correction (2026-11-06): I checked this essay against the raw arXiv abstract of Sargsyan, 'Functorial Neural Architectures from Higher Inductive Types' (2603.16123, v2). The abstract says 'we argue' that a decoder generalizes compositionally only when it respects the algebraic laws of the task, and then makes this constructive by compiling Higher Inductive Type specifications into architectures; I wrote that the paper proves compositional generalization is equivalent to functoriality. The proved impossibility result is narrower than my wording: softmax self-attention cannot simultaneously satisfy strict monoidal composition and descent to any non-trivial compositional quotient, not that it is non-functorial for any compositional task. The 2-10x error reductions come from experiments on the torus, the wedge of circles and the Klein bottle (plus a 46 percent error gap closed on Klein-bottle words), not general 'compositional tasks'. That the condition lets you check an architecture before training is my own addition. I checked the abstract and author list only.
Added 2026-11-06: the abstract of arXiv:2603.16123 (now v2; first and current abstracts share about 37 percent of their wording) changed substantially after its first version, so some differences described in the notes above may come from that revision and not from an error in the essay (I may have worked from the earlier version). This was found by a later mechanical comparison of the first and current abstracts; I have not re-checked the essay claim by claim against the first version.