Compositional Generalization via Structural Identification in a Category-Theoretic Framework

Akihiro Maeda; Thomas Seiller; Yohei Oseki

cs.CLAug 26, 2026

Compositional Generalization via Structural Identification in a Category-Theoretic Framework

Authors: Akihiro Maeda, Thomas Seiller, Yohei Oseki

Organizations: The University of Tokyo Tokyo, Japan · CNRS Paris, France

Abstract

Compositional generalization is usually evaluated through model accuracy. We instead ask which structural or lexical identifications make held-out COGS examples admissible from the structures observed in training. Sentences are represented as functors from syntactic addresses to lexical tokens, and selective collapses induce Kan extensions that propagate observed associations. Across 21 COGS generalization types, admissibility follows distinct identification profiles, while residual failures separate unsupported structural templates. These data-side diagnoses characterize what the training corpus licenses under specified identifications, without training a predictive model.

Figures & tables

Panel of Figure 1 — Figure 1: A COGS sentence is represented as a functor $F_{x}:\mathcal{A}_{x}\to\mathcal{W}_{x}$ . The prefix relation theme $\preceq$ theme.nmod_on is carried to the dependency cake $\to$ table . A corpus is a family of such functors; for computation, we reduce it to a relation $R\subseteq\mathcal{A}\times V$ , where $V$ is the vocabulary. The syntactic collapse $\sigma$ acts on the address side and the lexical collapse $\tau$ on the lexical side.

Map	Identification	Example
$\sigma_{\mathrm{id}}$	No identification	$\texttt{agent}\mapsto\texttt{agent}$
$\sigma_{\mathrm{rec}}$	Collapse recursive depth	$\texttt{ccomp.ccomp}\mapsto\texttt{ccomp}^{+}$
$\sigma_{\mathrm{last}}$	Retain only the final relation	$\texttt{ccomp.theme},\texttt{xcomp.theme}\mapsto\texttt{theme}$
$\sigma_{\mathrm{arg}}$	Identify argument roles	$\texttt{agent},\texttt{theme},\texttt{recipient}\mapsto\texttt{ARG}$
$\sigma_{\mathrm{role}}$	Identify broad structural roles	$\texttt{nmod\_in},\texttt{nmod\_on},\texttt{nmod\_beside}\mapsto\texttt{NMOD}$

Table 1: Structural identifications used in the analysis. Definitions are given in Appendix A

Generalization type	id	rec	last	arg	arg $+\tau$
Frame alternation (6)	0.878–0.903	0.878–0.903	0.888–0.914	0.890–0.914	1.000
Clausal embedding (1)	0.000	0.010	0.998	0.998	1.000
Argument-position shift (7)	0.000	0.000	0.000	0.998–1.000	1.000
Modifier-position shift (1)	0.025	0.025	0.604	0.920	0.922
Primitive-to-role (5)	0.000	0.000	0.000	0.000	1.000
Unbounded modifier depth (1)	0.000	0.003	0.220	0.220	0.222

Table 2: Coverage of COGS generalization types under successive structural and lexical identifications; bold marks the first operation at which each resolved type becomes substantially covered. Per-type results for all 21 cases are reported in Appendix D .

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

type	id	rec	last	arg	role	arg+ $\tau$	gate
passive_to_active	.878	.878	.888	.890	1.000	1.000	–
active_to_passive	.895	.895	.895	.895	1.000	1.000	–
unacc_to_transitive	.885	.885	.896	.898	1.000	1.000	–
obj_omitted_transitive_to_transitive	.885	.885	.896	.898	1.000	1.000	–
do_dative_to_pp_dative	.894	.894	.911	.911	.999	1.000	–
pp_dative_to_do_dative	.903	.903	.914	.914	.999	1.000	–

Appendix

Table 3: Per-type coverage for all 21 generalization cases. The gate column records the dominant residual obstruction after the argument collapse for types with coverage below 0.5: G1 denotes an unavailable collapsed address, G2 an unsupported structural template, and G3 an unsupported lexical value. All five primitive-to-role cases exhibit G3 failures and are resolved by

\tau

, whereas pp_recursion exhibits a G2 failure and remains largely unresolved.

\sigma_{\mathrm{role}}

is shown only as an over-coarsening control.

Generalization type	Associated identification	Transformer
Frame alternation (6)	none	0.38–0.99
Argument-position shift (7)	$\sigma_{\mathrm{arg}}$	0.30–0.87
Clausal embedding (1)	$\sigma_{\mathrm{last}}$	0.00
Modifier-position shift (1)	$\sigma_{\mathrm{arg}}$	0.00
Primitive-to-role (5)	$\tau$	0.00–0.17
Unbounded modifier depth (1)	unresolved	0.00

Appendix

Table 4: Data-side characterization versus published Transformer accuracy [ Kim and Linzen, 2020 ] .

Compositional Generalization

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

See all 113 papers

Structural Generalization on SLOG without Hand-Written Rules
Apr 28, 2026Zichao WeiNeural Cellular Automata Semantic Parsing
Saarland University
Type Diversity Enables Transformers to Generalise Compositionally
Sep 11, 2026Anssi Moisio, Mathias Creutz, Mikko KurimoTransformer Semantic Parsing
Aalto University · University of Helsinki
CoGe-GCD: Reframing Generalized Category Discovery with Compositional Generalization
Sep 9, 2026Luyao Tang, Jiewei Zheng, Kunze Huang +3Geometric Representation Learning Classification
The University of Hong Kong, Hong Kong SAR, China · Xiamen University, Xiamen, China · Shenzhen University, Shenzhen, China.

Apr 28, 2026J/K move · Enter open · S save

Structural Generalization on SLOG without Hand-Written Rules

Zichao Wei

Saarland University

Neural Cellular Automata Semantic Parsing Compositional Generalization

Open paper AskPDF arXiv

Structural generalization in semantic parsing requires systems to apply learned compositional rules to novel structural combinations. Existing approaches either rely on hand-written algebraic rules (AM-Parser) or fail to generalize structurally (Transformer-based models). We present an alternative requiring no hand-written compositional rules, based on a neural cellular automaton (NCA) with a discrete bottleneck: all compositional rules are learned from data through local iteration. On the SLOG benchmark, the system achieves an overall accuracy of

67.3 \pm 0.2\%

across 10 seeds (AM-Parser:

70.8 \pm 4.3\%

), with 11 of 17 structural generalization categories at

100\%

type-exact match, including three where AM-Parser scores

0

74\%

. Analysis reveals that all 5,539 failure instances reduce to exactly two mechanisms: novel combinations of wh-extraction context with reduced verb types, and modifiers appearing on the subject side of verbs. When we decompose results by CCG structural features, each sub-pattern either succeeds on all instances or fails on all. Intermediate scores (e.g.,

41.4\%

) are mixtures of structurally distinct CCG patterns, not partial generalization. These results suggest that CCG directed types provide higher resolution than SLOG's phenomenon-level categories for characterizing structural generalization, and that the success/failure boundary is determined by the coverage of directed operations in the training data.

Abstract

Compositional Generalization

Explore similar work

Structural Generalization on SLOG without Hand-Written Rules

Type Diversity Enables Transformers to Generalise Compositionally

CoGe-GCD: Reframing Generalized Category Discovery with Compositional Generalization