Functorial Neural Architectures from Higher Inductive Types

Karen Sargsyan

cs.LGMar 17, 2026

Functorial Neural Architectures from Higher Inductive Types

Authors: Karen Sargsyan

Organizations: Institute of Chemistry, Academia Sinica, Taipei, Taiwan

Abstract

Neural networks often learn the parts of a task but fail on novel combinations of those parts. We argue that this failure is architectural: a decoder generalizes compositionally only when it respects the algebraic laws of the task, i.e. when it descends from freely generated sequences to the quotient determined by those laws. We make this principle constructive by compiling Higher Inductive Type (HIT) specifications into neural architectures. Basepoints, path constructors, and 2-cells are mapped to base constraints, generator networks, structural concatenation, and learned homotopies. The resulting transport decoders are strict monoidal functors by construction: decoding a concatenated word is concatenation of independently generated loop segments. In contrast, we prove that softmax self-attention cannot simultaneously satisfy strict monoidal composition and descent to any non-trivial compositional quotient. Experiments on the torus, wedge of circles, and Klein bottle validate the predicted hierarchy: functorial decoders outperform non-functorial alternatives by $2$ -- $10\times$ , and a learned 2-cell closes a $46\%$ error gap precisely on words exercising the Klein-bottle relation. These results suggest that compositional generalization should be enforced as functorial structure in the architecture, rather than learned from examples alone.

Figures & tables

Panel of Figure 1 — Figure 1: The three HIT specifications. Each square presents the space by gluing together cells: corners are the basepoint $x_{0}$ , labelled edges are the path constructors $\mathrm{loop}_{a},\mathrm{loop}_{b}$ , and the interior is the 2-cell. In $T^{2}$ , both pairs of opposite edges are identified in the same direction; the interior surf witnesses $\mathrm{loop}_{a}\cdot\mathrm{loop}_{b}=\mathrm{loop}_{b}\cdot\mathrm{loop}_{a}$ . The wedge $S^{1}\vee S^{1}$ has two loops meeting at a single basepoint with no relating 2-cell. In the Klein bottle $K$ , the horizontal edges are identified in the same direction but the vertical edges in opposite directions—the orientation reversal that makes the interior rel witness $\mathrm{loop}_{b}\cdot\mathrm{loop}_{a}\cdot\mathrm{loop}_{b}^{-1}=\mathrm{loop}_{a}^{-1}$ . The three cases exhaust the structurally distinct possibilities: abelian with a 2-cell, free without one, and non-abelian with a non-trivial 2-cell.

Panel of Figure 2 — Figure 2: Transport vs. softmax attention as string diagrams, with three input tokens. Left: the transport decoder of Construction 3.2 applies one generator network $g_{w_{i}}$ per token wire; wires stay parallel and the output loop factors as the monoidal product $\gamma_{1}\oplus\gamma_{2}\oplus\gamma_{3}$ (Theorem 3.3 ). Right: softmax self-attention is a single morphism on the entire tensor product, with positive weights $\alpha_{ij}>0$ on every input/output pair (grey wires); each output position $\gamma^{\prime}_{i}$ depends on every input token, so the morphism does not factor as a monoidal product—this is the obstruction in Theorem 4.1 .

Architecture	Type	Compiled from HIT	Params	Why type-A or B?
Transf. (WC)	A	winding only	585K	Attn. mixes segments
Cover	A	winding only	205K	No composition
Transp. Attn.	A	winding + positions	585K	Correct positions, attn. mixes
Transport	B	winding + generators	170K	Struct. concatenation
Homotopy	B	all (incl. 2-cell)	195K	Concat. + learned $H$

Table 1: Architectures tested on

T^{2}

. The other two spaces use a subset of these (see Tables 3 , 4 ). “Compiled from HIT” indicates which level of Construction 3.2 the architecture implements: winding = hard topological constraint only, generators = independent loop networks, all = generators plus learned 2-cell

H

. Type-A decoders allow cross-segment information flow or lack compositional structure; type-B decoders compose independently generated segments.

Architecture	Type	$L{=}2$	$L{=}4$	$L{=}6$	$L{=}8$	$L{=}10$
Transf. (WC)	A	$1.89{\scriptstyle\pm.12}$	$1.42{\scriptstyle\pm.31}$	$1.42{\scriptstyle\pm.37}$	$1.53{\scriptstyle\pm.51}$	$1.54{\scriptstyle\pm.34}$
Cover	A	$2.15{\scriptstyle\pm.31}$	$1.65{\scriptstyle\pm.11}$	$2.07{\scriptstyle\pm.06}$	$1.98{\scriptstyle\pm.20}$	$1.91{\scriptstyle\pm.10}$
Transp. Attn.	A	$1.83{\scriptstyle\pm.18}$	$1.63{\scriptstyle\pm.17}$	$1.77{\scriptstyle\pm.21}$	$2.05{\scriptstyle\pm.19}$	$2.09{\scriptstyle\pm.13}$
Transport	B	$1.68{\scriptstyle\pm.22}$	$0.86{\scriptstyle\pm.12}$	$0.74{\scriptstyle\pm.03}$	$0.73{\scriptstyle\pm.03}$	$\mathbf{0.77{\scriptstyle\pm.03}}$
Homotopy	B	$1.68{\scriptstyle\pm.19}$	$0.93{\scriptstyle\pm.09}$	$0.74{\scriptstyle\pm.03}$	$0.74{\scriptstyle\pm.02}$	$\mathbf{0.80{\scriptstyle\pm.03}}$

Table 2: Torus

T^{2}

: Per-segment Chamfer distance

\bar{d}_{L}

(mean

\pm

std, 3 seeds) at increasing word length

L

. Training uses

L\leq 2

; test lengths

3

–

10

are never seen. Type-B decoders (below line) stabilize; type-A decoders (above) stagnate or degrade despite more parameters.

		Per-seg Chamfer $\bar{d}_{L}$			Circle acc. (%)
Architecture	Type	$L{=}2$	$L{=}6$	$L{=}10$	$L{=}2$	$L{=}10$
Transformer	A	$.152{\scriptstyle\pm.002}$	$.411{\scriptstyle\pm.027}$	$.537{\scriptstyle\pm.027}$	33	14
Sequential	A	$.010{\scriptstyle\pm.001}$	$.173{\scriptstyle\pm.021}$	$.297{\scriptstyle\pm.027}$	67	11
Transport	B	$.002{\scriptstyle\pm.001}$	$.018{\scriptstyle\pm.008}$	$\mathbf{.054{\scriptstyle\pm.019}}$	100	100

Table 3: Wedge of circles

S^{1}\vee S^{1}

(

\pi_{1}=F_{2}

, non-abelian): per-segment Chamfer and circle accuracy. Non-abelian structure dramatically amplifies the type-A/B gap. Full

L

-progression in Appendix D .

Architecture	Type	Canonical	Non-canonical
Cover	A	$1.57{\scriptstyle\pm.10}$	$1.96{\scriptstyle\pm.07}$
Transf. (WC)	A	$2.28{\scriptstyle\pm.35}$	$2.26{\scriptstyle\pm.36}$
Transport	B	$0.84{\scriptstyle\pm.03}$	$\mathbf{1.52{\scriptstyle\pm.08}}$
Homotopy	B	$0.82{\scriptstyle\pm.03}$	$\mathbf{0.82{\scriptstyle\pm.06}}$

Table 4: Klein bottle: per-segment Chamfer at

L=10

, split by word type. The homotopy decoder (type-B with proof term

H

) closes the gap on non-canonical words.

	$T^{2}$ ( $\mathbb{Z}^{2}$ )	$S^{1}\vee S^{1}$ ( $F_{2}$ )	$K$ ( $\mathbb{Z}\rtimes\mathbb{Z}$ )
Best type-B $\bar{d}_{10}$	$0.77$	$0.054$	$0.82$
Best type-A $\bar{d}_{10}$	$1.54$	$0.297$	$1.76$
Gap (best A / best B)	$2.0\times$	$5.5\times$	$2.1\times$
Transport vs. Homotopy	$\approx 1.0$	$\approx 1.0$	$\mathbf{1.85\times}$
2-cell needed?	No (abelian)	No (free)	Yes (relation)

Table 5: Cross-experiment summary at

L=10

. “Best A / best B” gives the tightest type comparison.

K

values in the first three rows are overall averages across canonical and non-canonical words; the Transport vs. Homotopy entry is the non-canonical ratio, where the 2-cell is exercised (Table 4 shows the split). The Klein bottle is the only space where the 2-cell matters.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Architecture	Type	$L{=}2$	$L{=}3$	$L{=}4$	$L{=}6$	$L{=}8$	$L{=}10$
Transformer	A	$.152{\scriptstyle\pm.002}$	$.245{\scriptstyle\pm.006}$	$.297{\scriptstyle\pm.022}$	$.411{\scriptstyle\pm.027}$	$.464{\scriptstyle\pm.039}$	$.537{\scriptstyle\pm.027}$
Sequential	A	$.010{\scriptstyle\pm.001}$	$.100{\scriptstyle\pm.005}$	$.129{\scriptstyle\pm.009}$	$.173{\scriptstyle\pm.021}$	$.247{\scriptstyle\pm.034}$	$.297{\scriptstyle\pm.027}$
Transport	B	$.002{\scriptstyle\pm.001}$	$.015{\scriptstyle\pm.010}$	$.012{\scriptstyle\pm.005}$	$.018{\scriptstyle\pm.008}$	$.030{\scriptstyle\pm.011}$	$.054{\scriptstyle\pm.019}$

Appendix

Table 6:

S^{1}\vee S^{1}

: per-segment Chamfer

\bar{d}_{L}

(mean

\pm

std, 3 seeds), full

L

-progression.

Architecture	Type	$L{=}2$	$L{=}3$	$L{=}4$	$L{=}6$	$L{=}8$	$L{=}10$
Transformer	A	33	19	16	19	12	14
Sequential	A	67	36	20	14	8	11
Transport	B	100	100	100	100	100	100

Appendix

Table 7:

S^{1}\vee S^{1}

: circle accuracy (%, mean over 3 seeds). Transport achieves 100% by construction.

Architecture	Type	$L{=}2$	$L{=}3$	$L{=}4$	$L{=}6$	$L{=}8$	$L{=}10$
Cover	A	$1.81{\scriptstyle\pm.13}$	$1.90{\scriptstyle\pm.04}$	$1.69{\scriptstyle\pm.04}$	$1.86{\scriptstyle\pm.06}$	$1.81{\scriptstyle\pm.13}$	$1.76{\scriptstyle\pm.07}$
Transf. (WC)	A	$1.80{\scriptstyle\pm.16}$	$1.84{\scriptstyle\pm.21}$	$1.84{\scriptstyle\pm.24}$	$2.03{\scriptstyle\pm.29}$	$2.28{\scriptstyle\pm.39}$	$2.27{\scriptstyle\pm.33}$
Transport	B	$1.54{\scriptstyle\pm.18}$	$1.51{\scriptstyle\pm.05}$	$1.25{\scriptstyle\pm.06}$	$1.24{\scriptstyle\pm.05}$	$1.18{\scriptstyle\pm.03}$	$1.17{\scriptstyle\pm.04}$
Homotopy	B	$1.43{\scriptstyle\pm.14}$	$1.10{\scriptstyle\pm.04}$	$0.97{\scriptstyle\pm.07}$	$0.85{\scriptstyle\pm.04}$	$0.79{\scriptstyle\pm.05}$	$0.82{\scriptstyle\pm.03}$

Appendix

Table 8: Klein bottle

K

: per-segment Chamfer

\bar{d}_{L}

on all test words (mean

\pm

std, 3 seeds).

Architecture	Type	$L{=}2$	$L{=}3$	$L{=}4$	$L{=}6$	$L{=}8$	$L{=}10$
Cover	A	$1.86{\scriptstyle\pm.20}$	$2.08{\scriptstyle\pm.11}$	$1.68{\scriptstyle\pm.07}$	$1.99{\scriptstyle\pm.08}$	$2.02{\scriptstyle\pm.08}$	$1.96{\scriptstyle\pm.07}$
Transf. (WC)	A	$1.84{\scriptstyle\pm.11}$	$1.93{\scriptstyle\pm.33}$	$1.87{\scriptstyle\pm.28}$	$1.96{\scriptstyle\pm.30}$	$2.32{\scriptstyle\pm.40}$	$2.26{\scriptstyle\pm.36}$
Transport	B	$1.73{\scriptstyle\pm.12}$	$1.82{\scriptstyle\pm.06}$	$1.37{\scriptstyle\pm.08}$	$1.45{\scriptstyle\pm.04}$	$1.44{\scriptstyle\pm.05}$	$1.52{\scriptstyle\pm.08}$
Homotopy	B	$1.38{\scriptstyle\pm.12}$	$1.13{\scriptstyle\pm.02}$	$0.97{\scriptstyle\pm.08}$	$0.83{\scriptstyle\pm.02}$	$0.75{\scriptstyle\pm.02}$	$0.82{\scriptstyle\pm.06}$

Appendix

Table 9: Klein bottle

K

: per-segment Chamfer on non-canonical words only (words where

b

precedes

a

, exercising the relation

bab^{-1}=a^{-1}

). The transport–homotopy gap isolates the proof term’s contribution.

Arch.	Comp.	Comm.	Reorder	Noncan.
Transf. (WC)	$4.05{\scriptstyle\pm.21}$	$0.24{\scriptstyle\pm.13}$	$4.37{\scriptstyle\pm.10}$	$2.04{\scriptstyle\pm 1.65}$
Cover	$4.25{\scriptstyle\pm.18}$	0.000	$4.96{\scriptstyle\pm.39}$	0.000
Transp. Attn.	$4.21{\scriptstyle\pm.14}$	$1.54{\scriptstyle\pm 1.39}$	$4.79{\scriptstyle\pm.28}$	$0.96{\scriptstyle\pm.56}$
Transport	$4.28{\scriptstyle\pm.13}$	0.000	$3.82{\scriptstyle\pm.07}$	0.000
Homotopy	$4.24{\scriptstyle\pm.19}$	0.000	$3.79{\scriptstyle\pm.13}$	0.000

Appendix

Table 10:

T^{2}

coherence battery. Exact zeros are architectural guarantees, not learned.

Compositional Generalization

Compositional generalization is the ability to combine learned parts and rules in ways that transfer to unseen combinations.

See all 113 papers

A Theoretical Analysis of Provable Compositional Generalization in Neural Networks: A Necessary and Sufficient Condition
May 5, 2025Yuanpeng LiCompositional Generalization
TPR-Attention for Combinatorial Generalization
Aug 31, 2026Melisa Civelekoğlu, Isabeau Prémont-SchwarzAttention Mechanisms Compositional Representation Learning
Universit´e Laval · Institut intelligence et donn´ees · Mila – Qu´ebec Artificial Intelligence Institute
Learning Sparse Compositional Functions with Norm-Constrained Neural Networks
May 25, 2026Shuo Huang, Lorenzo Fiorito, Lorenzo Rosasco +1Neural Network Generalization Hierarchical Representation Learning
MaLGa, DIMA, Università degli Studi di Genova, Genoa, Italy · CBMM, Massachusetts Institute of Technology, Cambridge, MA, USA

May 5, 2025J/K move · Enter open · S save

A Theoretical Analysis of Provable Compositional Generalization in Neural Networks: A Necessary and Sufficient Condition

Yuanpeng Li

Compositional Generalization

Open paper AskPDF arXiv

Compositional generalization

\unicode{x2013}

the ability to systematically process novel combinations of known components

\unicode{x2013}

is a hallmark of human intelligence; however, its theoretical foundation in neural networks is not yet well understood. This paper establishes a necessary and sufficient condition for provable compositional generalization, precisely characterizing its boundary. Conceptually, the condition consists of two principles: (i) structural alignment, where a model's computational graph aligns with a task's true compositional hierarchy, and (ii) unambiguous minimized representations, where each component encodes adequate but not redundant information on the training data. The result is fully proved and machine-verified in Lean 4 and holds even in few-shot and one-shot regimes. The necessity direction establishes that provable compositional generalization cannot circumvent these requirements, while the sufficiency direction yields a unified inductive bias that jointly governs architectural design, training data properties, and regularization strategies. Building on this condition, we develop an example algorithmic approach, illustrate it through a controlled minimal example, and further demonstrate the condition on the SCAN jump task. All conclusions are derived mathematically without reliance on empirical validation. Our work provides a theoretical characterization of provable compositional generalization.

Abstract

Compositional Generalization

Explore similar work

A Theoretical Analysis of Provable Compositional Generalization in Neural Networks: A Necessary and Sufficient Condition

TPR-Attention for Combinatorial Generalization

Learning Sparse Compositional Functions with Norm-Constrained Neural Networks