Transformers have dominated sequence processing tasks for the past seven years–most notably language modeling. However, the inherent quadratic complexity of their attention mechanism remains a significant bottleneck as context length increases. We review and distill the recent efforts to overcome this bottleneck, including advances in (sub-quadratic) attention variants, recurrent neural networks, state space models, and hybrid architectures. We critically analyze approaches regarding compute and memory complexity, benchmark results, and fundamental limitations to assess whether the dominance of pure-attention transformers may soon be challenged, which we consider possible, particularly in domain-specific and edge-device applications.
Figures & tables
Figure 1: The four types of dot-product attention alternatives identified in our survey, including examples. We further divide hybrid concepts (striped and fusion hybrids), and sub-quadratic attention variants (approximate and sparse attention) each in two major classes.
Figure 2: Different types of hybrids. (a) : block types using different primitives are connected in series. (b) : block types are connected in parallel.
Method
Training
Inference
Time
Space
Parallel
Time
Space
FFT-Convolution
O(Bndlog(dn))
O(Bnd)
Yes
O(ndlog(nd))
O(nd)
RNN
O(Bnd2)
O(Bnd)
No
O(d2) 2 2 2 Assuming the sequence has been processed already, only necessary once
O(nd)
Vanilla Transformer
O(B(n2d+nd2))
O(B(n2+nd))
Yes
O(n2d+d2n)
O(n2+nd)
LSH (Reformer)
O(Bd2nlogn)
O(Bnlogn+Bnd)
Yes
O(d2nlogn)
O(nlogn+nd)
FAVOR+ (Performer)
O(Bnd2logd)
O(Bndlogd+Bd2logd)
Yes
O(nd2logd)
O(ndlogd+d2logd)
Table 1: Overview on time & space complexities for training on a single batch and inference of a single token of different sequence-modeling mechanisms. n : sequence length; d : hidden dimension; B : batch size
Model
Benchmark Selection
0.7-1.5B
Size
MMLU
LMB
ARC-E
ARC-C
Wino.
Hella.
PIQA
Titans-MAG
760M
-
41.0
68.2
36.2
52.9
48.9
70.3
Griffin
1B
29.5
-
67.0
36.9
65.2
67.2
77.4
Llama3.2*
1B
32.1
63.0
-
-
60.7
63.7
-
GLA
1.3B
-
46.9
57.2
26.6
53.9
49.8
71.8
HGRN2
1.3B
-
49.4
58.1
28.1
52.3
51.8
71.4
Table 2: Performance comparison of recent pure quadratic attention LMs (highlighted with *) and subquadratic models of similar size. Best results for each parameter category are marked in bold , second-best results are underlined . Model names are in bold or underlined when they scored first or second at least once. Results are accuracy-based and rounded to one decimal point. For sources, see Section A.3
Transformers dominate modern sequence modeling, but their quadratic attention incurs substantial computational cost. Subquadratic architectures offer a scalable alternative. However, it remains unclear which designs yield the most effective sequence models. We compare three leading approaches: xLSTM, Mamba-2, and Gated DeltaNet. We evaluate these models on tasks with complex dependencies: (1) code-model pre-training, (2) distillation of code models from large language models, and (3) pre-training of time-series foundation models. Across these settings, xLSTM delivers the strongest overall performance. To explain xLSTM's advantage, we present a unified formulation and analyze the underlying architectural mechanisms, focusing on state tracking and memory dynamics. Our results show that xLSTM enables more flexible and stable memory correction via its gating scheme. We corroborate these findings on controlled synthetic length-generalization tasks. Overall, our findings indicate that xLSTM's gains on complex tasks stem from robust state tracking and accumulation.
Anamaria-Roberta Hartl, Levente Zólyomi, David Stap +6
The Softmax Attention operation in Transformer language models has a quadratic complexity in the sequence length and a growing state size in the form of KV cache, which becomes a bottleneck in long context scenarios. To overcome this limitation, alternative architectures with linear complexity and finite state size have been introduced, such as State-Space Models (SSMs), Linear Attention (LA), and Attention with Bounded-memory Control (ABC). Though linear models achieve similar language perplexity as Transformers, they are still behind in tasks which require retrieval or recall of specific information. In this work, we introduce Blurry Window Attention (BLA) a novel ABC method inspired by SSMs. BLA stores a frequency window from which a blurry KV history is reconstructed via interpolation using Dirichlet kernels. BLA can be understood as a generalization of Sliding Window Attention (SWA) depending on the Dirichlet kernels resolution or as a special case of the Gated Slot Attention (GSA), where the decay factor is implemented with Dirichlet kernels. We describe in details the theory and efficient implementation of BLA. On the Multi-Query Associate Recall (MQAR) synthetic task, we show that the state efficiency of BLA is 8× better than SWA and is competitive with popular linear attention models, and in the RegBench synthetic task, only BLA and SWA improve their performance as the state size grows among the linear models we tested.
Axel Laborieux, Christos Sourmpis, Juan Gabriel Kostelec +1
Huawei, Zurich, Switzerland · Huawei Advanced Computing and Storage Lab, Shenzhen, China
Linear attention transformers have become a strong alternative to softmax attention due to their efficiency. However, linear attention tends to be less expressive and results in reduced accuracy compared to softmax attention. To bridge the accuracy gap between softmax attention and linear attention, we manipulate Mamba-2, a very strong linear attention variant. We first simplify Mamba-2 down to its most fundamental and important components, evaluating which specific choices make it most accurate. From this simplified Mamba variant (Mamba-2S), we improve the A-mask and increase the order of the hidden state, resulting in a method, which we call 2Mamba, that is nearly as accurate as softmax attention, yet much more memory efficient for long context lengths. We also investigate elements to Mamba-2 that help surpass softmax attention accuracy. Code is provided for all our experiments.
Gabriel Mongaras, Eric C. Larson
Lyle School of Engineering Southern Methodist University Dallas, TX 75205