Abstract
Compositionality—the principle that the meaning of complex expressions is derived from their constituents and combination rules—is fundamental to human language and reasoning. However, neural networks often struggle with systematic generalization in compositional tasks. This paper introduces a formal mathematical framework to quantify compositionality using Computation DAGs (cDAGs) and the Locus of Influence (LoI). We theoretically analyze how different architectures, including RNNs and Transformers, vary in their ability to approximate hierarchical functions and generalize to unseen combinations. Our results establish bounds on approximation error and generalization, highlighting the trade-offs between architectural expressivity and compositional stability.
Introduction
While researchers generally agree that compositionality is vital for language processing, the field has lacked a precise mathematical definition. Existing benchmarks like SCAN or COGS show that standard models often fail to generalize to new combinations of known parts. This paper fills that gap by linking a model's internal structural complexity to its expressivity and generalization guarantees.
The cDAG Framework
The authors propose a neuro-symbolic definition of a compositional function consisting of four parts: a Token Encoder, a Computation DAG (cDAG), a Span Processor, and a Read-out Function. The cDAG defines the hierarchy of how inputs are combined.
Locus of Influence (LoI)
To quantify complexity, the authors introduce the Locus of Influence (LoI):
- Absolute LoI ($\delta$): Measures the sensitivity of the output to a specific input token. It accounts for path lengths in the cDAG and the "smoothness" of the processor.
- Relative LoI ($\beta$): Measures how much influence one token has compared to the average.
Architectural analysis reveals that unidirectional RNNs have an Absolute LoI that grows exponentially with sequence length, explaining their difficulty with long-range dependencies. In contrast, Tree-structured RNNs have a logarithmic $\delta$, making them more "compositionally efficient."
Architectural Analysis and Expressivity
Most standard models use an "input-agnostic" cDAG, where the structure of the computation doesn't change based on the content. The authors prove that these models struggle to approximate "input-dependent" functions (like those following a specific grammar) unless they have very high complexity.
Standard Transformers are viewed as highly connected, multi-layered cDAGs with a high $\delta$. While expressive, this high sensitivity makes them theoretically more prone to generalization failures. Sparse attention is identified as a way to reduce this complexity and potentially improve systematic generalization.
Theoretical Results
The paper culminates in two major theorems:
- Theorem 1 (Approximation): Establishes that the error in approximating an input-dependent function with an input-agnostic model is bounded by the ratio of $\delta/\beta$.
- Theorem 2 (Generalization): Provides a generalization bound showing that the difference between training error and true error is directly proportional to the compositional complexity $\delta$.
Conclusion
By formalizing compositionality through cDAGs and LoI, this work provides a theoretical basis for understanding the generalization limits of neural architectures. It suggests that achieving robust systematic generalization requires managing the Locus of Influence, potentially through more structured or adaptive computation graphs.
Summary updated