A Provable Expressiveness Hierarchy in Hybrid Linear-Full Attention
This provides a foundational theoretical perspective for understanding the capabilities and limitations of different attention mechanisms in transformers, which is crucial for researchers and practitioners in machine learning and AI.
The paper tackles the lack of theoretical characterization of expressive power in efficient attention mechanisms compared to full attention, establishing a provable hierarchy where an (L+1)-layer full attention network solves a multi-step reasoning task, but hybrid networks with L-1 full attention layers and 2^{3L^2} linear attention layers cannot.
Transformers serve as the foundation of most modern large language models. To mitigate the quadratic complexity of standard full attention, various efficient attention mechanisms, such as linear and hybrid attention, have been developed. A fundamental gap remains: their expressive power relative to full attention lacks a rigorous theoretical characterization. In this work, we theoretically characterize the performance differences among these attention mechanisms. Our theory applies to all linear attention variants that can be formulated as a recurrence, including Mamba, DeltaNet, etc. Specifically, we establish an expressiveness hierarchy: for the sequential function composition-a multi-step reasoning task that must occur within a model's forward pass, an ($L+1$)-layer full attention network is sufficient, whereas any hybrid network interleaving $L-1$ layers of full attention with a substantially larger number ($2^{3L^2}$) of linear attention layers cannot solve it. This result demonstrates a clear separation in expressive power between the two types of attention. Our work provides the first provable separation between hybrid attention and standard full attention, offering a theoretical perspective for understanding the fundamental capabilities and limitations of different attention mechanisms.