What makes Models Compositional? A Neuro-Symbolic Theoretical View (Extended Abstract)

Parikshit Ram, Tim Klinger, Alexander G. GrayLNSAI @ IJCAI 2024 · OpenReview

Abstract

While compositional generalization is a recognized challenge for modern language models, the field has lacked a rigorous mathematical framework to define and measure it. This paper introduces a neuro-symbolic approach that decomposes models into symbolic computation graphs and neural processing functions. By quantifying "compositional complexity" through the Locus of Influence (LoI), the authors provide a theoretical lens to analyze how different architectures, such as Transformers and RNNs, handle complex sequence processing and generalization.

Introduction

The inherent compositionality of language—building complex meanings from simpler units—is a cornerstone of human intelligence. For AI models to achieve true understanding, they must demonstrate compositional generalization (CG): the ability to generalize from limited examples to an infinite domain of novel combinations. Despite empirical evidence of failure in modern neural networks, the underlying reasons remain opaque due to the lack of formal definitions. This work bridges that gap by proposing a mathematical framework to quantify compositionality and its impact on generalization.

A Neuro-Symbolic Framework for Compositionality

The authors propose a modular definition of compositional functions that separates continuous neural components from discrete symbolic structures. This framework is built upon four pillars:

  1. Token Encoder: Projects input tokens into a latent space.
  2. Computation Directed Acyclic Graph (cDAG): A symbolic hierarchical graph that traces the step-by-step processing and combination of sequence elements.
  3. Span Processor: The neural component that combines latent representations into higher-order terms (e.g., merging word embeddings into phrase representations).
  4. Read-out Function: Maps final latent terms to the output space.
Two examples of cDAGs illustrating different hierarchical ways to process a sequence of five tokens.

To measure the complexity of these compositions, the authors introduce the Locus of Influence (LoI). LoI quantifies the sensitivity of the final output to individual input tokens by tracing paths through the cDAG. This leads to a formal metric for compositional complexity (δ), which characterizes the structural density of the model's computation.

Architectural Fingerprints and Generalization

A key insight of this framework is that different architectures possess distinct "architectural fingerprints" defined by their cDAG structures.

A comparison of various cDAG structures, representing the 'architectural fingerprints' of different sequence processing models.
  • RNNs vs. Transformers: Unidirectional RNNs typically exhibit linear cDAGs with low out-degrees, whereas Transformers utilize dense cDAGs where tokens interact globally across multiple layers.
  • Input-Dependent Routing: The framework highlights that models with fixed, input-agnostic cDAGs struggle to approximate functions requiring dynamic routing without a significant penalty in compositional complexity.
  • Generalization Bounds: The authors theoretically demonstrate that higher absolute compositional complexity (δ) correlates with a wider generalization gap. Specifically, models with dense, highly interconnected structures (like Transformers) may face greater challenges in systematic generalization compared to more structured, recursive models.

Key Results and Implications

The paper provides theoretical complexity bounds for standard architectures, linking structural density to performance guarantees:

  • Unidirectional RNNs: Absolute LoI is bounded by $c^{L-1}$, with a relative LoI of $1/2$.
  • Transformers: Absolute LoI is bounded by $(Lc)^M$, with a relative LoI of $1/L$.

These results formally link architectural choices to "productivity"—the ability to generalize to sequences longer than those seen during training. The framework proves that a flexible, recursive cDAG is a prerequisite for such length generalization.

Conclusion

This theoretical work provides a much-needed foundation for understanding compositionality in neural networks. By separating the symbolic "routing" from neural "processing," the authors offer a path toward designing architectures with better generalization guarantees. Future work will extend this framework to delve deeper into the mechanics of length generalization and empirical validation of the proposed complexity metrics.

Summary updated

BibTeX
@inproceedings{ram2024what,
  author = {Parikshit Ram and Tim Klinger and Alexander G. Gray},
  title = {{What makes Models Compositional? A Neuro-Symbolic Theoretical View (Extended Abstract)}},
  booktitle = {LNSAI @ IJCAI},
  year = {2024},
  url = {https://openreview.net/forum?id=eF5xpd8OCP},
}
Figure