Compositional Reasoning

The capacity to recombine known concepts in novel ways to understand unseen combinations. Unlike pattern matching, which relies on statistical correlations, systematicity requires an algebraic understanding of structure.

• Productivity: Generating an infinite number of novel expressions from a finite set of primitives.
• Substitutivity: Understanding that swapping components changes meaning predictably.
• Fodor & Pylyshyn's Challenge: Classic argument that connectionist models fail without compositional structure.

The mechanism by which discrete, reusable concepts are dynamically linked to roles within a larger structure. This prevents the binding problem, where features of different objects are incorrectly mixed.

• Role-Filler Independence: A 'red circle' and 'blue square' require binding 'red' to 'circle' independently of 'blue' to 'square'.
• Tensor Product Representations: A mathematical formalization using vector spaces to bind fillers to roles via tensor products.
• Dynamic Inference: Enables on-the-fly comprehension of novel object-relation combinations without retraining.

Learning latent spaces where individual generative factors of variation are encoded in separate, independent dimensions. A change in one factor corresponds to a change in a single latent variable.

• Factor Separation: Isolating shape, color, and size into distinct vector dimensions.
• β-VAE: A variational autoencoder variant that applies a stronger constraint on latent information bottleneck to encourage disentanglement.
• Zero-Shot Transfer: Disentangled factors can be recombined to synthesize data with novel attribute combinations unseen during training.

A class of architectures that dynamically assemble task-specific networks from a library of reusable neural modules based on the compositional structure of the input.

• Layout Prediction: A parser analyzes the query to determine the logical structure and which modules to connect.
• Module Specialization: Individual modules are trained to perform specific functions like find[color] or describe[object].
• Visual QA Application: Excels at answering complex questions about images by composing visual attention and classification modules.

Standardized datasets designed to expose failures in systematicity by testing models on held-out combinations of known primitives.

• SCAN: A navigation task where models must interpret novel command sequences like 'jump twice' after training on 'jump' and 'twice' separately.
• COGS (Compositional Generalization Challenge): Tests semantic parsing by requiring generalization to new syntactic structures with known words.
• gSCAN: A grounded version of SCAN adding visual context and complex adverbs, revealing brittleness in standard sequence-to-sequence models.

Standardized datasets designed to expose failures in systematicity by testing models on held-out combinations of known primitives.

• SCAN: A navigation task where models must interpret novel command sequences like 'jump twice' after training on 'jump' and 'twice' separately.
• COGS (Compositional Generalization Challenge): Tests semantic parsing by requiring generalization to new syntactic structures with known words.
• gSCAN: A grounded version of SCAN adding visual context and complex adverbs, revealing brittleness in standard sequence-to-sequence models.

Models must compositionally combine object recognition, spatial relationship understanding, and attribute comparison to answer questions about unseen image compositions.

• CLEVR benchmark: Tests counting, comparison, and spatial reasoning with synthetic 3D objects
• GQA dataset: Requires multi-step relational reasoning over real-world scene graphs
• Models must generalize to novel object-attribute combinations never seen during training

Large language models decompose natural language specifications into primitive programming constructs and compose them into executable programs with novel variable bindings and control flow.

• MBPP and HumanEval benchmarks measure compositional generalization to unseen function signatures
• Models must recombine known API calls, loops, and conditionals in configurations absent from training
• Systematic generalization failures occur when models encounter novel combinations of familiar sub-tasks

Automated theorem provers apply learned proof tactics and lemma combinations to derive novel proofs, requiring the composition of known inference rules in previously unseen sequences.

• Lean and Coq environments test the ability to chain tactics into valid proofs
• Neuro-symbolic architectures combine neural guidance with symbolic verification
• Compositional failures manifest as inability to recombine known lemmas for novel theorems

Robotic agents must parse compositional instructions like "pick up the red block to the left of the blue cylinder" by combining object recognition, spatial relation primitives, and action sequences.

• ALFRED benchmark: Tests compositional task completion in household environments
• Requires systematic recombination of known actions with novel object-goal pairings
• Failure modes include inability to chain sub-tasks when object references are compositionally novel

Natural language interfaces to databases must compositionally map queries to SQL or SPARQL by combining table schemas, aggregation functions, and filter conditions in novel configurations.

• Spider and WikiSQL benchmarks test cross-domain compositional generalization
• Models must recombine known SQL clauses for unseen database schemas
• Template-based approaches fail when queries require novel nesting of sub-clauses

Graph neural networks must compositionally reason about functional groups and their interactions to predict properties of novel molecules, combining known chemical substructures in unseen configurations.

• OGB and MoleculeNet benchmarks test generalization to molecules with novel scaffold combinations
• Compositional models learn primitive group contributions and recombine them for property estimation
• Failure occurs when models rely on rote memorization of training scaffolds rather than compositional rules

The defining objective of compositional reasoning: the ability to understand and produce novel combinations of known primitives without explicit training on those specific combinations.

• Key benchmark: SCAN, COGS, and gSCAN datasets test this capability
• Failure mode: Standard seq2seq models often fail when lexical items appear in new syntactic positions
• Solution space: Neural module networks and discrete symbolic programs outperform monolithic models
• Real-world impact: Enables zero-shot transfer to unseen instruction compositions in robotics

A representational learning objective where individual latent dimensions correspond to independent, interpretable factors of variation in the data.

• Relevance to composition: Disentangled primitives are the atomic building blocks that a compositional system recombines
• Techniques: β-VAE, FactorVAE, and TC-VAE enforce statistical independence in the latent space
• Evaluation: Metrics like Mutual Information Gap (MIG) and DCI Disentanglement score quantify separation
• Challenge: Unsupervised disentanglement without inductive biases remains theoretically impossible in the general case

A perceptual framework where scenes are decomposed into discrete, persistent entities with independent properties and relations, rather than holistic pixel arrays.

• Slot-based models: Slot Attention and IODINE learn to bind features to object slots without supervision
• Compositional generalization: Object-centric representations enable reasoning about novel object configurations and counts
• Relation networks: Once objects are individuated, relational reasoning modules can compose pairwise comparisons
• Benchmarks: CLEVR, CATER, and Physion test compositional visual reasoning with object-centric priors

The formal mapping between linguistic expressions and their denotations in a world model or execution environment, ensuring that composed phrases correspond to composed meanings.

• Formal foundation: Montague semantics and lambda calculus provide the compositional algebra for meaning construction
• Modern implementations: Dynamic neural semantic parsers that ground language to executable SQL, SPARQL, or robot action sequences
• Compositionality principle: The meaning of a complex expression is a deterministic function of the meanings of its parts and their syntactic combination rule
• Failure analysis: Non-compositional models exploit spurious dataset correlations rather than learning true semantic composition