Research map / Large language models / AI and society

Towards a Formal Theory of Representational Compositionality

ICML 2025 · Large language models › AI and society · approach: Social-science view of AI evaluation

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes representational compositionality, a Kolmogorov-complexity-based definition scoring a representation as the ratio of its total complexity to the complexity of its semantics given intrinsic discrete parts, and validates it on synthetic lookup-table and grammar representations, emergent languages, and natural-language sentence embeddings.

Problem

Compositionality is widely invoked but lacks a formal, quantitative definition that handles context-sensitivity, degrees of compositionality, and the origin of constituent parts in neural representations.

Approach

Define compositionality of a representation as K(Z)/K(Z|W), where W are intrinsic discrete parts from the shortest compressing program, so compositional representations are expressive yet describable as a simple function of parts; a language-system variant uses externally given sentences W^L.

Key results

• Representational compositionality C(Z) behaves as intuition predicts across lookup-table and grammar experiments (e.g., decreasing with disentanglement and grammar width/depth), whereas topological similarity violates several intuitions.
• Iterated learning yields lower-complexity, more compositional emergent languages under C_L(Z); non-iterated languages score the minimum value of 1.
• On translated COCO captions, relative C_L(Z) is similar across English, French, Spanish, German and Japanese, with Japanese slightly higher; topological similarity gives near-zero values and Japanese at -0.2.

Measured effects reported in the paper

Surprising findings

• Topological similarity is largest for a vocabulary size of 1 and decreases with sentence length, contrary to intuition.
• Topological similarity for Japanese is a strong negative outlier (-0.2), while the proposed metric finds roughly equal compositionality across the languages studied.

Limitations

• Representational compositionality is uncomputable because it involves Kolmogorov complexities; only the language-system variant C_L(Z) was estimated in practice.
• Estimating C(Z) via discrete auto-encoders may be sensitive to architecture, hyperparameters and data quantity.
• Definition is restricted to discrete parts; extension to continuous parts is left open.

Experimental setup

Datasets: COCO captions synthetic lookup-table representations synthetic context-free grammar representations multi-agent emergent language game data

Benchmarks: synthetic lookup table representations synthetic grammar representations emergent language referential game COCO captions translated to French, Spanish, German, Japanese

Metrics: representational compositionality C(Z) language system compositionality C_L(Z) topological similarity

Baselines: topological similarity

Builds on: Kolmogorov complexity topological similarity iterated learning Ren et al. 2023 structure-preserving maps

Closest papers by meaning

• Diagnosing the Compositional Knowledge of Vision Language Models from a Game-Theoretic View (ICML 2024 · similarity 0.87)
• CtD: Composition through Decomposition in Emergent Communication (ICLR 2025 · similarity 0.86)
• Compositional Causal Reasoning Evaluation in Language Models (ICML 2025 · similarity 0.86)
• When does compositional structure yield compositional generalization? A kernel theory. (ICLR 2025 · similarity 0.85)
• A Theory of Formalisms for Representing Knowledge (AAAI 2025 · similarity 0.85)
• Does Data Scaling Lead to Visual Compositional Generalization? (ICML 2025 · similarity 0.85)