하이브리드 선형-전체 어텐션에서의 증명 가능한 표현력 계층 구조

A Provable Expressiveness Hierarchy in Hybrid Linear-Full Attention

트랜스포머는 대부분의 최신 대규모 언어 모델의 기반이 됩니다. 표준 전체 어텐션의 2차 복잡성을 완화하기 위해 다양한 효율적인 어텐션 메커니즘, 예를 들어 선형 어텐션 및 하이브리드 어텐션이 개발되었습니다. 그러나 이러한 어텐션 메커니즘의 전체 어텐션에 대한 표현력은 아직 엄밀하게 이론적으로 규명되지 않았습니다. 본 연구에서는 이러한 어텐션 메커니즘 간의 성능 차이를 이론적으로 분석합니다. 우리의 이론은 Mamba, DeltaNet 등과 같이 순환 구조로 표현될 수 있는 모든 선형 어텐션 변형에 적용됩니다. 특히, 우리는 표현력의 계층 구조를 확립합니다. 순차적 함수 결합, 즉 모델의 순전파 과정 내에서 수행되어야 하는 다단계 추론 작업의 경우, $L+1$ 레이어의 전체 어텐션 네트워크는 충분하지만, $L-1$ 레이어의 전체 어텐션과 현저히 많은 수($2^{3L^2}$)의 선형 어텐션 레이어를 혼합한 어떠한 하이브리드 네트워크도 이를 해결할 수 없습니다. 이 결과는 두 가지 유형의 어텐션 간의 명확한 표현력 차이를 보여줍니다. 본 연구는 하이브리드 어텐션과 표준 전체 어텐션 간의 최초의 증명 가능한 차이를 제시하며, 다양한 어텐션 메커니즘의 기본적인 능력과 한계를 이해하는 데 필요한 이론적 관점을 제공합니다.

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.