Source-linked AI summary
Compositional Generalization via Structural Identification in a Category-Theoretic Framework
Akihiro Maeda, Thomas Seiller, Yohei Oseki
TL;DR
Compositional generalization is difficult to assess from model accuracy alone because held-out examples combine familiar components in novel ways. This paper uses functorial sentence representations and selective structural or lexical collapses with Kan extensions to test data-side admissibility across COGS. Across 21 generalization types, distinct identification profiles emerge, while residual failures expose unsupported structural templates without training a predictive model.
Problem
Model accuracy does not identify which training-data distinctions must be identified for a held-out COGS case to generalize.
Method
The paper represents sentences as functors and applies externally specified structural and lexical collapses whose Kan extensions propagate observed associations.
Results
Across 21 COGS types, distinct identification profiles emerge: structural path, argument role, and lexical class provide different sufficient abstractions, while modifier-depth failures remain mainly structural.
Takeaways & Limitations
The analysis characterizes what COGS training data licenses under specified identifications and provides candidate inductive biases for systematic generalization.
Takeaways & Limitations
The identifications are externally specified, and the structural and semantic representation is derived from COGS logical forms rather than induced from raw sentences.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper reframes compositional generalization as identifying which structural or lexical distinctions make held-out COGS examples admissible from training data. It formalizes this diagnosis with category theory and distinguishes data-licensed generalization from what a learner realizes.
- COGS evaluates novel grammatical roles, unseen combinations of familiar structures, and recursive structures beyond training observations.
- The framework asks which structural or lexical identifications make held-out cases compatible with training data, rather than relying only on model accuracy.
- Sentences are represented as functors from syntactic addresses to word categories, with syntactic and lexical collapses determining the tested Kan extensions.
- Each COGS generalization type receives an operational identification profile, and unresolved cases indicate structural or lexical obstructions.
- The resulting operations characterize what training data licenses separately from what a learner actually realizes and provide candidate inductive biases for future models.
2 Categorical formulation of compositional generalization
The paper models sentences as structured functors and generalization as selective identification of syntactic addresses or lexical classes. Kan extensions then propagate observed address–vocabulary associations, while complete coverage requires both structural and lexical admissibility.
- COGS logical forms provide dependency relations from which each token receives a syntactic address, while sentences retain predicates and grammatical relations.
- Addresses are finite dependency-label sequences ordered by prefix, and a sentence template is a finite prefix-closed set recording co-occurring syntactic positions.
- A sentence functor maps its address category to a token-occurrence category while preserving dependency structure and separating positions from lexical realizations.
- Structural collapses identify addresses and lexical collapses identify token classes, with tested abstractions including recursion, final labels, and grammatical argument roles.
- The address–vocabulary relation records observed lexical items at each address, and a left Kan extension propagates assignments across collapse fibres.
- A held-out sentence is covered only when its collapsed structural signature is supported and its lexical assignment belongs to the admissible set.
3 Empirical Analysis on COGS
Deterministic coverage over 21 COGS generalization types reveals distinct identification profiles. Most residual failure for unbounded modifier depth is structural, and resolving it requires a diagnostic collapse that risks overgeneralization.
- Experimental setup: Coverage is computed from the full training split without training a predictive model, using successive identity, recursion, last-label, argument, and lexical collapses.
- Identification profiles: Frame alternations are largely admissible without extra identification, while clausal embedding reaches 0.998 under σlast and argument shifts reach 0.998–1.000 under σarg.
- Identification profiles: All five primitive-to-role cases remain inadmissible under structural collapses and reach 1.000 only after lexical identification by τ.
- Residual structural obstruction: Unbounded modifier depth reaches only 0.220 under σarg and 0.222 after adding τ, with residual failures localized primarily to unsupported structural templates.
- Residual structural obstruction: The diagnostic σrole raises modifier-depth coverage to 0.985 by identifying nominal-modifier relations, but collapses the template inventory to two templates and risks overgeneralization.
4 Prior studies
Prior work provides model-accuracy evaluations and broader connections between formal structure, lexical co-occurrence, embedding geometry, and compositionality. The paper treats its coverage analysis as complementary rather than directly comparable to exact-match accuracy.
- Coverage measures whether specified identifications license held-out examples, whereas Transformer exact-match accuracy measures whether a trained model produces the correct logical form.
- Formal concept and lattice structures have been found in lexical co-occurrence representations and LLM embedding geometry, suggesting a broader connection to compositionality.
5 Conclusion and Limitations
The analysis characterizes COGS compositional generalization through identifications that license unseen combinations via Kan extension, while presenting these operations as candidate inductive biases rather than a trained predictive model.
- Across COGS, compositional generalization is characterized by identifications that license unseen combinations through Kan extension.
A COGS and the address system
COGS pairs sentences with logical forms, whose grammatical relations define rooted address structures. The framework formalizes these structures, lexical assignments, and controlled collapses for deterministic generalization analysis.
- COGS representation: COGS is a semantic parsing benchmark pairing source sentences with logical forms that specify lexical predicates and grammatical relations.
- Address space: The address space is a free monoid of structural-label paths, with ROOT as the unit and addresses recording root-to-token paths.
- Closed sentence templates: Sentence templates are finite prefix-closed address sets, so every occurring position includes all positions on its path from the root.
- Structural collapses: A structural collapse identifies selected addresses, including recursive, last-label, and argument-role collapses.
- Structural collapses: Collapsed structural signatures retain occurrence multiplicity, distinguishing controlled identification from ordinary set-based image formation.
- Lexical collapse: Lexical collapse identifies items sharing COGS-provided lexical attributes and is externally supplied rather than learned.
- Generalization split: The 21 COGS evaluation types comprise frame alternations, argument-position shifts, modifier and clausal-embedding shifts, primitive-to-role types, and unbounded modifier depth.
B Kan extensions induced by collapses
Kan extensions propagate training address–word associations across selected structural or lexical collapse fibres. The computation uses discrete address objects, while the original prefix order remains responsible for templates and functorial structure.
- Kan extension: A left Kan extension is a universal construction that extends a functor along a map while preserving a natural transformation.
- Specialization to the corpus representation: For computation, the address category is reduced to a discrete set of objects with a vocabulary-valued corpus assignment.
- Fibre-wise form: Because the computation is discrete, structural Kan extensions operate fibrewise using unions and intersections of observed lexical assignments.
- Extension induced by a structural collapse: The experiments use the upper extension as the least fibre-constant assignment containing the observed relation.
- Extension induced by a structural collapse: Newly admitted address–word pairs record combinations licensed by the selected structural identification but absent from direct training observations.
- Lexical collapse: Lexical extension lets a word inherit address associations from all items in its lexical-collapse fibre.
- Joint collapse: Joint structural and lexical collapse evaluates admissibility using the extended relation induced by both fibres.
- Relation to the full address category: The computation ignores non-identity morphisms of the full address category; an order-sensitive Kan extension is left for future work.
C Galois closure and the Boolean Isbell interpretation
The paper models sentence-level admissibility through Galois closure and interprets the resulting closure as a Boolean Isbell nucleus. This closure freely recombines coordinate-wise admissible lexical values.
- Galois closure: The construction defines complete lexical assignments, coordinate constraints, and a satisfaction relation between them.A section satisfies a coordinate constraint when its token at that address belongs to the specified set.
- Galois closure: The induced antitone Galois connection makes X 7→X↑↓ a closure operator on sentence assignments.The connection is characterized by X ⊆ Y↓ if and only if Y ⊆ X↑.
- Closed sets: Closed sets are rectangular products whose coordinate projections contain exactly the values permitted at each address.The closure adds assignments obtained by freely recombining values already present in coordinate-wise projections.
- Admissible combinations: Kan extension first constructs locally admissible lexical sets, which are then combined into complete sentence-level assignments.When the local sets are nonempty, the resulting Adm(s) is a fixed point of the closure and therefore the extent of a formal concept.
- Boolean Isbell interpretation: Under the Boolean profunctor, the Isbell conjugacy induces the same closure, so admissible products are objects of the associated Boolean Isbell nucleus.The nucleus consists of the fixed points of X 7→X↑↓, with each fixed extent determining a corresponding intent.
- Beyond Boolean admissibility: The framework is binary in its present form, while quantale enrichment would replace Boolean incidence with graded compatibility.This provides a direction for incorporating graded semantic or selectional relations.
D Per-type coverage for all generalization cases
Per-type results show that COGS generalization cases become admissible under different identification operations, while residual failures distinguish unavailable addresses, unsupported templates, and inadmissible lexical values.
- Per-type coverage: 1.000 coverage is reached for all five primitive-to-role cases only after lexical identification by τ.They remain at zero under every tested structural collapse because the residual obstruction is lexical.
- Per-type coverage: cp_recursion is almost completely resolved by σlast, whereas pp_recursion remains limited by an unsupported structural template.The corresponding diagnostic labels are G2 for unsupported structural templates and G3 for unsupported lexical values.
- Aggregate coverage: 0.2555, 0.3439, 0.6923, and 0.9592 are the aggregate coverages under the identity map, σlast, σarg, and σarg+τ, respectively.Different generalization groups become admissible at different abstraction stages, so coverage alone does not select an appropriate collapse.
- Aggregate coverage: 0.7610 coverage under σrole is treated as an over-coarsening control because it reduces the observed structural inventory to only two templates.The control illustrates that higher aggregate coverage need not indicate an appropriate generalization operation.
D.1 Comparison with the prior study
Table 4 places the proposed data-side characterization alongside published Transformer accuracy to relate the two analyses without treating their quantities as numerically comparable.
- Table 4 compares the proposed data-side characterization with grouped Transformer accuracies reported by Kim and Linzen [2020].
- The table relates operational profiles identified in the analysis to previously reported model behavior.
- The quantities have different meanings and are not intended for numerical comparison.
Use of LLM-based tools.
LLM-based assistants supported literature exploration, categorical formulation refinement, and mathematical-derivation checks, while the authors retained responsibility for verification and conclusions.
- LLM-based assistants supported literature exploration, categorical formulation refinement, and checking mathematical derivations.
- The authors independently verified mathematical claims, references, experimental procedures, and conclusions.