What makes Models Compositional? A Theoretical View: With Supplement

Understand

Compositionality is thought to be a key component of language, and various compositional benchmarks have been developed to empirically probe the compositional generalization of existing sequence processing models.

• These benchmarks often highlight failures of existing models, but it is not clear why these models fail in this way.
• In this paper, we seek to theoretically understand the role the compositional structure of the models plays in these failures and how this structure relates to their expressivity and sample complexity.
• We propose a general neuro-symbolic definition of compositional functions and their compositional complexity.