enter image description here

In this pretty neat article https://lena-voita.github.io/nlp_course/seq2seq_and_attention.html I saw the claim that one of the reasons of transformer architecture to be popular is the fact that it's reading all input at once as O(1) (obviously amount of work is M x M x d where M x d is input size) but according picture only Encoder part can do so. The Decoder is clearly working in a recurrent way reading its own output from previous steps, so its overall amount of work is actually O(M x M x M x d).

  1. So Decoder part make much more work (by factor of M) than Encoder.
  2. Transformer basically (if we forget its blowing complexity as argument of input length) is RNN model with build-in attention.

Or I'm missing something?

Also, please explain why does Transformer have so complex architecture? Can the Transformer Encoder part do the same thing in case of the output has the same size as the input?

  • 2
    $\begingroup$ I'm not sure there's a satisfying answer to "why does Transformer have so complex architecture?" If people knew of a simpler architecture that achieved comparable results, researchers would use that one instead. But no one's found such an architecture yet. $\endgroup$
    – Sycorax
    Commented Mar 4, 2021 at 16:01
  • $\begingroup$ @Sycorax Let me introduce analogy. Someone writes that in 3d world, 3 legs for a table is enough to be stable, so far so good, and then he suddenly says that he will make a thing with 222 legs because 222 >= 3. $\endgroup$ Commented Feb 21, 2022 at 14:17
  • 1
    $\begingroup$ That seems like a great demonstration of my point — we built a 222 leg stool, and no one’s worked out how to make a 3-legged one yet, without giving up some essential performance. $\endgroup$
    – Sycorax
    Commented Feb 21, 2022 at 14:51
  • $\begingroup$ When I read their paper, I didn't see any attempts to build a stool with 122 legs instead of 222, did you? $\endgroup$ Commented Feb 22, 2022 at 9:08

1 Answer 1


The encoder-decoder architecture is not essential to transformers. The original paper used it because they designed it for a translation task, but this is not necessary. For classification tasks (sequence-to-value) you can use an encoder-only model like BERT, for text generation a decoder-only model (indeed this is what GPT is). These are architecturally almost the same, except in a decoder model you mask the top right half of the attention matrix, so that tokens can't attend to future tokens. It turns out that a decoder-only model can also learn to do seq2seq tasks like translation if you prompt it with the input sequence.

The decoder is autoregressive in the same way as an autoregressive RNN: you feed it the input sequence and also all of the tokens it has already generated in the previous inferences. In this sense, each new token you generate is an additional inference, which adds to the cost. But this is also the case with RNNs.

You could train a model to generate entire utterances on top of a transformer encoder, which would require only 1 inference per sentence, but this would probably not perform that well. In particular for a vocabulary size of $10^4$ and a sentence length of 10 tokens, you have $10^{40}$ possible output sentences. There's no way to train a distribution over this huge space that would generalize well without factorizing token by token.

The key innovation of transformers that makes them perform better than autoregressive RNNs is the self-attention mechanism: this effectively means the model sees the entire input sequence at once. You compute the keys, queries and values of every token, then compute the attention. Therefore, the model can relate information across arbitrary distances in the context window. This is totally different from an RNN or LSTM model, where the information must flow through the hidden states of each unit. (see also this question) At least, this is how people usually think about it. This paper claims that masked transformers with a linear variant of attention are effectively RNNs, so perhaps the divide is not as essential as everyone thinks.

As for "why does Transformer have so complex architecture?" with respect to the transformer block and attention mechanism itself: I feel like this is not entirely understood and it's justified pragmatically based on its performance. Long-range dependencies certainly have something to do with it: for a context length $m$, there are $O(m^2)$ possible relations between 2 words. The self-attention mechanism can use information from all of them. There is a lot of work trying to make the compute sub-quadratic using ideas like exploiting the sparsity of the attention matrix. But the fundamental idea of self-attention is kept, and it's about making it more efficient.

I'm not aware of anything like the universal approximation theorem that specifically explains the expressive power of transformers, but here's some recent work in this direction. They look at how very small toy transformers perform and try to understand what's going on at the weight level. It turns out that even small 2-layer transformers (without any MLP layers) can learn a very general "induction schema" of the form [A][B]...[A]->[B], which allows them to generalize previously unseen examples encountered in the prompt, even if they are completely out of distribution w.r.t. training. This schema is probably much more difficult to express without self-attention. They also propose an interesting description of transformers in terms of communication streams between attention heads that I haven't seen elsewhere.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.