Answers.Body: <p>An RNN processes words one by one. For example on the sentence &quot;man eats dog&quot;, it will:</p>
  <ol>
  <li>Fully process &quot;man&quot;, producing an output <span class="math-container">$y_1$</span> and hidden units <span class="math-container">$h_1$</span>.</li>
  <li>Fully process &quot;eats&quot;, now using also the previous output and/or hidden units.</li>
  <li>Finally process &quot;dog&quot;, again using the previous output and/or hidden units <span class="math-container">$y_2$</span> and <span class="math-container">$h_2$</span>.</li>
  </ol>
  <p>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.</p>
  <p>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 <span class="math-container">$k_i$</span> of the <span class="math-container">$i$</span>th word, we multiply its embedding vector <span class="math-container">$e_i$</span>by a fixed matrix <span class="math-container">$M$</span>: <span class="math-container">$$k_i = M e_i$$</span> In fact we can first concatenate the embedding vectors into a matrix <span class="math-container">$E$</span> with components <span class="math-container">$E_{ki}$</span> being the <span class="math-container">$k$</span>th component of the embedding vector <span class="math-container">$e_i$</span> of the <span class="math-container">$i$</span>th word. This way all key vectors can be obtained at once as <span class="math-container">$$K = M E$$</span> with <span class="math-container">$K$</span> decomposing into components in the same way as <span class="math-container">$E$</span>.</p>
  <p>Note that matrix multiplication is highly parallelizable: a given component in the matrix <span class="math-container">$K$</span> depends on only one row of <span class="math-container">$M$</span> and one column of <span class="math-container">$E$</span>.</p>
  <p>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).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-07-31T16:13:58.387Z
Answers.LastActivityDate: 2021-07-31T16:13:58.387Z
Answers.UserDisplayName: Jansen
Body: <p>When compared to an RNN seq-to-seq model, people always say the Transformer is parallelizable. In the original <a href="https://papers.nips.cc/paper/2017/file/3f5ee243547dee91fbd053c1c4a845aa-Paper.pdf" rel="nofollow noreferrer">Attention Is All You Need</a> paper, it also said that</p>
  <blockquote>
  <p>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 <span class="math-container">$h_t$</span>, as a function of the previous hidden state <span class="math-container">$h_{t−1}$</span> and the input for position <span class="math-container">$t$</span>. This inherently sequential nature precludes parallelization within training examples</p>
  </blockquote>
  <p>I use the <a href="https://jalammar.github.io/illustrated-transformer/" rel="nofollow noreferrer">The illustrated Transformer</a> to help to explain my question here. It said (You can search those sentences):</p>
  <blockquote>
  <p>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.</p>
  </blockquote>
  <p><strong>However</strong>, actually in the self-attention layer, in order to calculate the select V, it needs the <em>key</em> values of all time steps! So each &quot;time step&quot; is not fully independent. There exist an operation in the layer that depends on the output, here is the key from all &quot;time step&quot;.</p>
  <p>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 &quot;time step&quot; or each token to wait for the others. Yes, it is better, but why do they call it parallelizable?</p>
  
Tags: <transformer><attention><implementation>
Title: Why people always say the Transformer is parallelizable while the self-attention layer still depends on outputs of all time steps to calculate?
UserDisplayName: palazzo train
ThreadText: # Why people always say the Transformer is parallelizable while the self-attention layer still depends on outputs of all time steps to calculate?
  
  (Asked by: username_0 on 2021-07-29)
  
  When compared to an RNN seq-to-seq model, people always say the Transformer is parallelizable. In the original [Attention Is All You Need](https://papers.nips.cc/paper/2017/file/3f5ee243547dee91fbd053c1c4a845aa-Paper.pdf) 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](https://jalammar.github.io/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?
  
  **Tags:** transformer, attention, implementation
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-07-31. Score: 1
  
  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).
  
  
  ---
  
  