# Why people always say the Transformer is parallelizable while the self-attention layer still depends on outputs of all time steps to calculate?

When compared to an RNN seq-to-seq model, people always say the Transformer is parallelizable. In the original Attention Is All You Need paper, it also said that

Recurrent models typically factor computation along the symbol positions of the input and output sequences. Aligning the positions to steps in computation time, they generate a sequence of hidden states $$h_t$$, as a function of the previous hidden state $$h_{t−1}$$ and the input for position $$t$$. This inherently sequential nature precludes parallelization within training examples

I use the The illustrated Transformer to help to explain my question here. It said (You can search those sentences):

Here we begin to see one key property of the Transformer, which is that the word in each position flows through its own path in the encoder. There are dependencies between these paths in the self-attention layer. The feed-forward layer does not have those dependencies, however, and thus the various paths can be executed in parallel while flowing through the feed-forward layer.

However, actually in the self-attention layer, in order to calculate the select V, it needs the key values of all time steps! So each "time step" is not fully independent. There exist an operation in the layer that depends on the output, here is the key from all "time step".

In the original paper, the same block is repeated 6 times. That means there are at least 6 points where the flow of independent operation of each "time step" or each token to wait for the others. Yes, it is better, but why do they call it parallelizable?

An RNN processes words one by one. For example on the sentence "man eats dog", it will:

1. Fully process "man", producing an output $$y_1$$ and hidden units $$h_1$$.
2. Fully process "eats", now using also the previous output and/or hidden units.
3. Finally process "dog", again using the previous output and/or hidden units $$y_2$$ and $$h_2$$.

Since the outcome of the first word is used as an input to the second, we must wait until it's done before starting computation on the second, and so on.

In self-attention, the output of say word 3 still depends on the previous (and subsequent) words as you say. However the dependence is much simpler: to obtain the key $$k_i$$ of the $$i$$th word, we multiply its embedding vector $$e_i$$by a fixed matrix $$M$$: $$k_i = M e_i$$ In fact we can first concatenate the embedding vectors into a matrix $$E$$ with components $$E_{ki}$$ being the $$k$$th component of the embedding vector $$e_i$$ of the $$i$$th word. This way all key vectors can be obtained at once as $$K = M E$$ with $$K$$ decomposing into components in the same way as $$E$$.

Note that matrix multiplication is highly parallelizable: a given component in the matrix $$K$$ depends on only one row of $$M$$ and one column of $$E$$.

So in short, the reason transformers are parallelizable while RNNs are not is not that they do not depend on earlier (or later) words, but rather that the dependence is linear, while for an RNN it is highly nonlinear (i.e. several layers of an affine transformation followed by a nonlinearity).