# Why does transformer has such a complex architecture?

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?

• 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.
– Sycorax
Commented Mar 4, 2021 at 16:01
• @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. Commented Feb 21, 2022 at 14:17
• 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.
– Sycorax
Commented Feb 21, 2022 at 14:51
• When I read their paper, I didn't see any attempts to build a stool with 122 legs instead of 222, did you? Commented Feb 22, 2022 at 9:08

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.
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.