Transformers achieve remarkable performance in several tasks but due to their quadratic complexity, with respect to the input's length, they are prohibitively slow for very long sequences. To address this limitation, we express the self-attention as a linear dot-product of kernel feature maps and make use of the associativity property of matrix products to reduce the complexity from $\mathcal{O}\left(N^2\right)$ to $\mathcal{O}\left(N\right)$, where $N$ is the sequence length. We show that this formulation permits an iterative implementation that dramatically accelerates autoregressive transformers and reveals their relationship to recurrent neural networks. Our linear transformers achieve similar performance to vanilla transformers and they are up to 4000x faster on autoregressive prediction of very long sequences.
Metadata: arXiv. Abstracts retain their original authors’ rights.
In the conversation
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
This is a form of linear attention (https://arxiv.org/abs/2006.16236) that approximates standard scaled dot-product attention to arbitrary precision, by adding Taylor terms in an efficient manner. Each additional Taylor term improves the approximation. Efficiency is achieved by exploiting certain mathematical symmetries that become evident only after decomposing the standard formulation of attention into an expression over chains of tensor products. The github repository's README walks through examples. The first example is with 8 Taylor terms.
> Who out there is working on ... infinite history?
Many people are still working on improving RNNs, mostly in academia. Examples off the top of my head:
* RWKV: https://arxiv.org/abs/2006.16236 / https://arxiv.org/abs/2404.05892 https://arxiv.org/abs/2305.13048
* Linear attention: https://arxiv.org/abs/2503.14456
* State space models: https://arxiv.org/abs/2312.00752 / https://arxiv.org/abs/2405.21060
* Linear RNNs: https://arxiv.org/abs/2410.01201
Industry OTOH has gone all-in on Transformers.
There is a LOT of effort in the research community currently:
1. Improving the Self-Attention in the Transformer as is, keeping the quadratic complexity, which has some theoretical advantage in principle[1]: The most hyped one probably DeepSeek's Multi-Latent Attention[15], which kind of is Attention still - but also somehow different.
2. Linear RNNs: This starts from Linear Attention[2], DeltaNet[3], RKWV[4], Retention[5], Gated Linear Attention[6], Mamba[7], Griffin[8], Based[9], xLSTM[10], TTT[11], Gated DeltaNet[12], Titans[13].
They all have an update like: C_{t} = F_{t} C_{t-1} + i_{t} k_{t} v_{t}^T with a cell state C and output h_{t} = C_{t}^T q_{t}. There's a few…
Read the full comment
tricks that made these work and now being very strong competitors to Transformers. The key here is the combination of an linear associative memory (aka Hopfield Network, aka Fast Weight Programmer, aka State Expansion...) and pushing it into a sequence with gating similar to the original LSTM (input, forget, output gate) - while here this is only dependent on the current input not the previous state for linearity. The linearity is needed to make it sequence-parallelizable, there are efforts now to add non-linearities again, but let's see. Their main benefit+downside both is that they have a fixed-size state, and therefore linear (vs Transformer-quadratic) time complexity.
For larger sizes they have become popular in hybrids with Transformer (Attention) Blocks, as there are problems with long context tasks [14]. Cool thing is they can also be distilled from pre-trained Transformers with not too much performance drop [16].
3. Along the sequence dimension most things can be categorized in these two. Attention and Linear (Associative Memory Enhanced) RNNs are heavily using Matrix Multiplications and anything else would be a waste of FLOPs on current GPUs. The essence is how to store information and how to interact with it, there might be still interesting directions as other comments show. Other important topics that go into the depth / width of the model are: Mixture of Experts, Iteration (RNNs) in Depth[17].
Disclaimer: I'm author of xLSTM and we recently released a 7B model [18] trained at NXAI, currently the fastest linear RNN at this scale and performance. Happy to answer more questions on this or the current state in this field of research.
[1] https://arxiv.org/abs/2008.02217
[2] https://arxiv.org/abs/2006.16236
[3] https://arxiv.org/pdf/2102.11174
[4] https://github.com/BlinkDL/RWKV
[5] https://arxiv.org/abs/2307.08621
[6] https://arxiv.org/pdf/2312.00752
[7] https://arxiv.org/abs/2312.06635
[8] https://arxiv.org/pdf/2402.19427
[9] https://arxiv.org/abs/2402.18668
[10] https://arxiv.org/abs/2405.04517
[11] https://arxiv.org/abs/2407.04620
[12] https://arxiv.org/abs/2412.06464
[13] https://arxiv.org/abs/2501.00663
[14] https://arxiv.org/abs/2406.07887
[15] https://arxiv.org/abs/2405.04434
[16] https://arxiv.org/abs/2410.10254
[17] http://arxiv.org/abs/2502.05171
[18] https://huggingface.co/NX-AI/xLSTM-7b
To further problematize this question (which I don't feel like I can actually answer), consider this paper: "Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention" - https://arxiv.org/pdf/2006.16236
What this shows is that actually a specific narrow definition of transformer (a transformer with "causal masking" - see paper) is equivalent to an RNN, and vice versa.
Similarly Mamba (https://arxiv.org/abs/2312.00752), the other hot architecture at the moment, has an equivalent unit to a gated RNN. For performance reasons, I believe they use an equivalent CNN during training and an RNN during inference!
Transformers are turing complete: https://arxiv.org/abs/1901.03429
Additionally, Transformers are RNNs: https://arxiv.org/abs/2006.16236
Transformers are turing complete RNNs, as are the Neocortex.
There are differences like spiking vs non-spiking neurons, universal vs non-universal activation, the effects of brain waves, bicameralism, etc. But these differences may or may not be important depending on the topic of discussion. Additionally, the differences increasingly disappear as transformers are increasingly augmented with functionally equivalent systems.
^^ See above comment and "Transformers are RNNs" paper to convince yourself.
There are various ways of seeing how transformer architectures work.
For the past data, using a temporal causal mask, you can compute all past features as they would have been seen by applying the causal mask, which allows you to seemingly do all the past computations in parallel, which hide the sequential aspect of it.
What I've described correspond to the the simpler subvariant figure 1 of "Attention is all you need" https://arxiv.org/pdf/2006.16236.pdf , of the transformer architecture in the case where you don't give the past as input to the input branch, put rather prepend it to the output,…
Read the full comment
which is the what people usually do in practice (see llama) ). If you want to use both branches of the transformer architecture, so that you can do filtering and smoothing (aka not using a causal mask) for the past data, it creates a "bottleneck" in your architecture, as you synthesize all the past into a finite sized context vector that you then use in the right branch of the transformer.
But alternatively you can loop along the time dimension first, and make the sequence more apparent. Due to how the (causally mask) transformer architecture is defined this gives exactly the same computation. It's just some loop reordering.
For the generation part, the sequential aspect is more evident as token are produce one by one sequentially and feedback to the transformer for the next token prediction.
The key component is the linear attention[1] and residual connections.
[1] https://arxiv.org/abs/2006.16236
> Transformers achieve remarkable performance in several tasks but due to their quadratic complexity, with respect to the input's length, they are prohibitively slow for very long sequences. To address this limitation, we express the self-attention as a linear dot-product of kernel feature maps and make use of the associativity property of matrix products to reduce the complexity from (N2) to (N), where N is the sequence length. We show that this formulation permits an iterative implementation that dramatically accelerates autoregressive transformers and reveals their relationship to recurrent neural networks. Our linear transformers achieve similar performance to vanilla transformers and they are up to 4000x faster on autoregressive prediction of very long sequences.
They are also efficient at inference-time. On GPUs the difference is noticeable only for sequences of length > 1024 (2048 for reformer since it adds some operations for hashing) thanks to the massive parallelism of GPUs amortizing the quadratic effect of the "usual" self-attention mechanism.
[edit]
Linformer (https://arxiv.org/pdf/2006.04768.pdf) is a different project from the one linked in https://linear-transformers.com/ (Transformers are RNNs https://arxiv.org/pdf/2006.16236.pdf).
TL;DR: The authors show that if you simplify Mamba so its state-space layer uses a diagonal matrix A that is a scalar times the identity matrix, the state-space transformation can be expressed as a form of causal linear attention.[a] That's the duality the authors refer to in the title. The key practical benefit is that it enables more efficient (faster) training on GPUs.
---
[a] https://arxiv.org/abs/2006.16236
Dao and Gu show that if you simplify Mamba so its state-space layer uses a diagonal matrix A_t that is a scalar times the identity matrix, i.e., A_t = a_t I, the state-space transformation can be expressed as a form of causal linear attention[a] by compounding coefficients a_1 ... a_t at each time step t. The equivalence of the simplified state-space layer and causal linear attention constitute the duality the authors refer to in the title. By taking advantage of this duality, Mamba-2 can be trained more efficiently, i.e., faster than original Mamba on GPUs.
Theoretical stuff aside, Mamba-2's performance seems to scale slightly better than original Mamba:…
Read the full comment
https://tridao.me/assets/img/2024-05-31-mamba-2/pile_8k_mamb...
Here's the code implementing Mamba-2: https://github.com/state-spaces/mamba/blob/main/mamba_ssm/mo...
Great work by Tri Dao (of FlashAttention fame) and Albert Gu, as usual.
The key question, for me and many others, is whether Mamba, Mamba-2, RWKV, and other linear RNN / linear attention models will ever match the performance of standard Softmax attention. My understanding and experience is that all the linear attention models out there [b] still underperform Softmax attention on things like recall tasks.[c]
---
[a] https://arxiv.org/abs/2006.16236
[b] https://github.com/topics/linear-attention / https://github.com/topics/linear-attention-model -- this list is by no means complete!
[c] https://arxiv.org/abs/2402.01032
> They don’t have any internal state
This is a common misconception : they do have internal state.
Transformers are RNNs : section 3.4 (page 5) https://arxiv.org/pdf/2006.16236.pdf
>As there is no hidden state, no "memory" or "intention" can be passed to the future
This is probably your misconception : "Transformers are RNNs" https://arxiv.org/pdf/2006.16236.pdf (see section 3.4)
Even though an inner state is not specified explicitly like in a LSTM, for a transformer it's possible to view the inner state as implicitly defined as the inner features (deterministically derived from the layers weights) applied to the past inputs.
Therefore transformers can learn to do the task by learning to remember a,b,ab to this inner state and write them in order ab,a,b (Though to train it you'll probably have to give it an initial random context to be able to…
Read the full comment
produce different sequences : From this source of entropy it will learn to produce 2 hidden variables which it will use to produce a,b,and ab)
I concede that it will not be an easy task to learn in this way, and that it's probably easier to train a chain of thought model where you will allow it to use its output to remember the state (by writing it down), instead of having to memorize in its weights. So if you train it to produce a,b,ab,a,b and then another transformer to extract the last 3 outputs a*b,a,b it become very easy.
Artificial intelligence (AI) researchers have been developing and refining large language models (LLMs) that exhibit remarkable capabilities across a variety of domains and tasks, challenging our understanding of learning and cognition.
Recent work has demonstrated substantial gains on many NLP tasks and benchmarks by pre-training on a large corpus of text followed by fine-tuning on a specific task.
Despite their massive size, successful deep artificial neural networks can exhibit a remarkably small difference between training and test performance.
Fast compilation is important when compilation occurs at runtime, such as query compilers in modern database systems and WebAssembly virtual machines in modern browsers.