A Provable Expressiveness Hierarchy in Hybrid Linear-Full Attention

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.

Large language models rely on a mechanism called "attention". Standard attention is powerful but slows down dramatically for long inputs. To speed things up, engineers often use faster, lightweight alternatives, such as linear attention or mix the fast and standard methods together. However, a rigorous understanding of whether these shortcuts sacrifice problem-solving ability compared to the original has been lacking. We studied tasks that require step-by-step reasoning entirely within the model's internal processing, like repeatedly looking up facts and composing them. We mathematically proved that even if you add an enormous number of fast linear-attention layers, they cannot compensate for missing just one standard attention layer. We also showed that certain sparse attention designs, which skip over parts of the input to save time, fundamentally struggle with tasks that need comparing every pair of items. Our results provide a formal proof that these efficiency tricks come with unavoidable trade-offs. This doesn't mean they are useless, but it gives a clearer map of where they fall short. We hope this understanding will guide the design of future models that remain fast without losing the ability to reason deeply.