Abstract
Compositionality—the principle that the meaning of a complex expression is determined by its parts and the rules for their combination—is a hallmark of human intelligence but remains a significant challenge for artificial neural networks. While empirical benchmarks like SCAN and COGS highlight failures in systematic generalization, a rigorous theoretical explanation for these failures has been lacking. This paper introduces a formal neuro-symbolic framework using Computation Directed Acyclic Graphs (cDAGs) to quantify compositionality. We define a new metric, the Locus of Influence (LoI), and prove that a model's systematic generalization error is intrinsically linked to its structural complexity. Our analysis reveals why hierarchical architectures like Tree-RNNs excel at compositional tasks while standard Transformers, despite their success in other domains, struggle due to their "flat" influence structure.
Introduction
Modern Large Language Models (LLMs) demonstrate remarkable capabilities in natural language processing, yet they frequently fail at "compositional generalization." For instance, a model might learn the meanings of "jump" and "run twice" but fail to interpret "jump twice" if it has not encountered that specific combination during training. This suggests that while models can map inputs to outputs, they do not necessarily learn the underlying compositional rules.
Previous research has largely relied on empirical testing on benchmarks such as SCAN, CFQ, and COGS. This work provides a theoretical foundation to understand how internal model architecture dictates the ability to learn and generalize compositionally, moving beyond trial-and-error benchmarks toward a formal "Physics of AI."
Theoretical Framework: cDAGs and LoI
The authors define a compositional function $f(X)$ through four distinct components:
- Token Encoder ($e$): Converts input atoms into a continuous latent space.
- Computation Directed Acyclic Graph (cDAG $D(X)$): The symbolic part of the model that defines the hierarchy of how tokens are combined.
- Span Processor ($g$): The neural component that recursively processes nodes in the cDAG.
- Read-out Function ($h$): Maps the final latent terms to the output space.
To quantify the impact of structure on performance, the paper introduces the Locus of Influence (LoI). This metric measures how much a single input token "ripples" through the network to affect the final output:
- Absolute LoI ($\delta$): The total sensitivity of the output to a specific input token.
- Relative LoI ($\beta$): The proportion of influence one token has compared to all others in the sequence.
Architectural Analysis
By calculating LoI for different architectures, the authors rank models by their "compositional complexity." The analysis reveals a stark contrast between hierarchical and non-hierarchical models:
- RNNs: Standard unidirectional RNNs exhibit a compositional complexity that grows exponentially with sequence length ($c^{L-1}$), making them highly unstable for long sequences.
- Tree-structured Models: Tree-RNNs and similar architectures maintain logarithmic complexity ($c^{\log L}$), which is much more manageable and aligns with human-like hierarchical reasoning.
- Transformers: Standard Transformers are "input-agnostic," meaning their computation structure remains fixed regardless of the input's inherent grammar. They exhibit a "flat" influence where every token influences the output equally ($\beta = 1/L$).
Results and Discussion
The paper provides a formal proof (Theorem 2) showing that systematic generalization error is directly proportional to the model's Absolute LoI ($\delta$). Essentially, higher structural complexity makes it mathematically harder for a model to generalize systematically.
Complexity Comparison Table
| Model | IDC (Input-Dependent) | $\delta$ (Absolute LoI) | $\beta$ (Relative LoI) |
|---|---|---|---|
| U-RNN | No | $c^{L-1}$ (Exponential) | $1/2$ |
| Tree-RNN | Yes | $c^{\log L}$ (Logarithmic) | $1/L$ |
| CNN + Pool | Partial | $c^{\log L}$ (Logarithmic) | $\sim 2/L$ |
| Transformer | No | $(Lc)^M$ (Polynomial) | $1/L$ |
The mathematical evidence suggests that the global attention mechanism, while beneficial for general tasks, prevents Transformers from achieving the "localism" required for deep, hierarchical composition. This explains why they struggle with tasks that follow a specific grammar or parse tree.
Conclusion
This research marks a significant step toward predicting model behavior based on structural DNA. While Transformers dominate current AI, their inherent "flatness" poses a fundamental mathematical barrier to strict compositionality. Future work will explore how models might learn to dynamically generate cDAG structures (learning to parse) and how the framework can be extended to non-cleanly-separable sub-problems where input meanings overlap.
Summary updated