What Makes Models Compositional? A Theoretical View

Parikshit Ram, Tim Klinger, Alexander G. Gray

Abstract

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. We then show how various existing general and special purpose sequence processing models (such as recurrent, convolution and attention-based ones) fit this definition and use it to analyze their compositional complexity. Finally, we provide theoretical guarantees for the expressivity and systematic generalization of compositional models that explicitly depend on our proposed definition and highlighting factors which drive poor empirical performance.

Introduction

Compositionality—the principle that the meaning of a complex expression is determined by the meanings of its constituent parts and the rules used to combine them—is fundamental to human language. While empirical benchmarks like SCAN, CFQ, and COGS have repeatedly demonstrated that modern neural models struggle with systematic generalization, the field has lacked a rigorous mathematical framework to explain these failures. This paper addresses this gap by proposing a formal neuro-symbolic definition of compositionality, allowing for a theoretical analysis of how architectural choices dictate a model's ability to generalize to unseen combinations of known atoms.

A Neuro-Symbolic Framework for Compositionality

The authors define a compositional function $f(X)$ through four primary components that decompose the sequence processing pipeline:

  1. Token Encoder ($e$): Maps input atoms (tokens) into a latent vector space.
  2. Computation DAG (cDAG $D$): A directed acyclic graph that specifies the hierarchy and order in which tokens are combined. This graph represents the "recipe" for the computation.
  3. Span Processor ($g$): A recursive neural module that processes nodes in the cDAG, combining latent representations from child nodes into parent nodes.
  4. Read-out Function ($h$): Maps the final latent terms from the cDAG's root nodes to the output space.
Examples of different computation DAGs (cDAGs) representing hierarchical combinations of input tokens.

By formalizing models in this way, we can categorize architectures (RNNs, CNNs, Transformers) into a $(k, q, m, \delta, \beta)$-compositional class. Here, $k$ represents the in-degree (span size), $q$ the out-degree (localism), and $m$ the number of layers.

The Locus of Influence (LoI)

The core theoretical innovation is the Locus of Influence (LoI), which quantifies the sensitivity of the output to specific input tokens:

  • Absolute LoI ($\delta$): Measures the total influence of a single token on the final output by summing the influence across all possible paths in the cDAG. A high $\delta$ indicates that the model is highly sensitive to that specific input.
  • Relative LoI ($\beta$): Measures a token's influence relative to the total influence of all tokens in the sequence.

Complexity and Generalization

The paper establishes a critical link between the structure of the cDAG and the model's ability to generalize. Theorem 2 proves that generalization error is directly proportional to the Absolute LoI ($\delta$). If a model's computation graph is too dense or deep, it becomes hypersensitive to specific training examples, leading to poor systematic generalization on unseen structures.

A dense cDAG structure illustrating high connectivity, characteristic of models with high Absolute Locus of Influence like Transformers.

The Transformer Paradox

Transformers present a unique case in this framework. Because of their global attention mechanism, every token can influence every other token across multiple layers, resulting in a very high Absolute LoI. This explains their immense expressivity and success on large-scale datasets but also highlights why they often fail on compositional benchmarks: they require vast amounts of data to "prune" the dense graph into the correct compositional structure. In contrast, models with sparser inductive biases (like Tree-RNNs or CNNs) have lower, more stable LoIs, which facilitates better generalization with fewer samples.

Key Results and Architectural Comparisons

The theoretical analysis yields a complexity hierarchy for common architectures:

  • Unidirectional RNNs: Exhibit exponential Absolute LoI ($c^{L-1}$), making them extremely sensitive to early tokens and prone to forgetting in long sequences.
  • Tree-RNNs & CNNs: Feature polynomial or logarithmic Absolute LoI ($c^{\log L}$), providing a more stable foundation for generalization.
  • Transformers: Possess a complexity of $(Lc)^M$. While polynomial in sequence length $L$, the depth $M$ creates a highly complex influence landscape.

Furthermore, Theorem 1 demonstrates that if a task requires an input-dependent computation (such as parsing a context-free grammar), models with fixed, input-agnostic structures (like standard RNNs) will always suffer from a non-zero approximation error that scales with the LoI ratio.

Conclusion

This work provides a mathematical lens through which we can understand the trade-offs between expressivity and generalization. By showing that sparsity in the computation graph is a key driver of systematicity, the authors provide a theoretical justification for the development of models with more structured, sparse inductive biases. Future work remains in understanding how these optimal computation graphs can be learned dynamically from raw data rather than being pre-defined.

Summary updated

Abstract

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. We then show how various existing general and special purpose sequence processing models (such as recurrent, convolution and attention-based ones) fit this definition and use it to analyze their compositional complexity. Finally, we provide theoretical guarantees for the expressivity and systematic generalization of compositional models that explicitly depend on our proposed definition and highlighting factors which drive poor empirical performance.
BibTeX
@inproceedings{ram2024what,
  author = {Parikshit Ram and Tim Klinger and Alexander G. Gray},
  title = {{What Makes Models Compositional? A Theoretical View}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=9oYYDy2i5d},
}
Figure