Answers.Body: <p>A recurrent neural network (RNN) depends on the previous hidden state from the previous time step. That is, an RNN is a function of both the data for the sequence at time <span class="math-container">$t$</span> and the hidden state from time <span class="math-container">$t-1$</span>. This means that we cannot compute the <span class="math-container">$t$</span>th hidden state without calculating the <span class="math-container">$t-1$</span>th state, and the <span class="math-container">$t-1$</span>th state without the <span class="math-container">$t-2$</span>th state, and so on.</p>
  <p>In contrast to this, a transformer is able to fully parallelise the processing of the sequence because it does not have this recursive relationship, i.e. a transformer is not a recursive function -- the recursive nature of the sequence is processed in other ways, such as through positional encoding. We can see this by the way self attention works.</p>
  <p>If we first consider the general attention mechanism framework, then we have a query <span class="math-container">$q$</span> and a set of paired key-value tuples <span class="math-container">$\textbf{k}_1, ..., \textbf{k}_n$</span> and <span class="math-container">$\textbf{v}_1, ..., \textbf{v}_n$</span>. In general, for each key, we will apply some attention function <span class="math-container">$\beta$</span> (such as a neural network) to obtain attention scores, <span class="math-container">$a_i = \beta(\textbf{q}, \textbf{k}_i)$</span>. We then define an attention vector <span class="math-container">$\textbf{a}$</span> where the <span class="math-container">$i$</span>th element is the <span class="math-container">$i$</span>th attention score, and we take a softmax of this vector to obtain attention weights <span class="math-container">$\alpha_i$</span> where <span class="math-container">$\alpha_i$</span> is the <span class="math-container">$i$</span>th element of <span class="math-container">$\mbox{softmax}(\textbf{a})$</span>. The output of the attention mechanism for query <span class="math-container">$\textbf{q}$</span> is then the weighted sum <span class="math-container">$\sum_{i=1}^n \alpha_i \textbf{v}_i$</span>.</p>
  <p>Now that we have the necessary background for an attention mechanism, we can look at self attention which is the backbone of Transformer. If we have a sequence denoted by <span class="math-container">$\{\textbf{x}_1, ..., \textbf{x}_n\}$</span>, then we can define a set of queries, keys and values to be these <span class="math-container">$\textbf{x}_i$</span> values. Note that previously we only had a single query, but here we will have multiple queries which is really how Transformer is able to parallelise the processing of the sequence. If we define <span class="math-container">$\textbf{Q}, \textbf{K}, \textbf{V}$</span> to be the matrices of the queries, keys and values (e.g. the <span class="math-container">$i$</span>th row of <span class="math-container">$\textbf{Q}$</span> corresponds to the <span class="math-container">$i$</span>th query, and similarly for the others). Self attention is as simple as performing attention over these query, key and values -- the name <em>self</em> comes from the fact that the queries, keys and values are all the same and represent the <span class="math-container">$i$</span>th element of the sequence. Now, we can write the above attention mechanism as <span class="math-container">$a_{i, j} = \beta(Q, K)$</span> where we now have a matrix of attention scores (because we have <span class="math-container">$i$</span> queries and <span class="math-container">$i$</span> keys the matrix will be square), and we can take softmax row-wise to get the attention weights (again, this will be an <span class="math-container">$i\times i$</span> matrix). If we call the matrix of attention weights <span class="math-container">$\textbf{A}$</span> then the output of a self attention layer will be given by <span class="math-container">$\textbf{A} \textbf{V}$</span>. As you can see, there is no recursive nature here and this is all parallelisable, e.g. it can be broken up and put onto multiple GPU's at the same time -- this would not be possible with an RNN as you would have to wait for the output of the previous layer.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-02T21:11:08.943Z
Answers.Text: please someone let me know if I have messed up the orders of my matrix multiplications.
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-03-12T12:24:46.890Z
Answers.Text: @abcd kind of, yes. The RNN has access to information from previous time steps through the hidden state, but if you look at how this is updated (in e.g. LSTMs which use a gating mechanism) then it starts to lose more information about time $t$ at time $t+k$ as $k$ increases. This isn't wholly true in transformers, as they attend to every previous token in the context window.
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-03-12T16:54:30.580Z
Answers.Text: I'm less sure on them but I think the same problem would happen. For really long sequences, the hidden state would start to lose information (I think).
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-03-13T20:56:56.793Z
Answers.Text: @abcd kind of hard to answer in a comment, probably it would require a writing out of the equations used in attention (perhaps you could ask it in a question and either myself or someone else will answer it), but basically if you look at how self-attention works, you can see that they attend to every token in the sequence without any loss of information (e.g. there is no attempt to collect all prior information in a single dynamic state)
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-02T21:10:54.150Z
Answers.LastActivityDate: 2021-12-02T21:10:54.150Z
Answers.UserDisplayName: David
Answers.Body: <p>The issue with Recurrent models is that they don't parallelization during training. 
  Sequential models performs better with more memory but faces problem in learning long-term memory dependencies. </p>
  
  <p>On the other hand Transformers take into account of <strong>self attention</strong> which boosts the speed of how fast the model can translate from one sequence to another and establishes dependencies b/w input and output and focus on relevant parts of the input sequence, which in turn eliminates recurrence and convolution unlike RNNs where sequential computation inhibits parallelization.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-09-17T14:01:33.983Z
Answers.Text: This answer does not provide much insight into how transformers are "more parallelizable" than RNNs. You say "unlike RNNs where sequential computation inhibits parallelization", but that's not very useful because you don't explain why transformers avoid the issue and why "sequential computation" is really the problem. You talk about many things that are irrelevant to answer the question and only give a few words to answer the question, which are unclear.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-11T11:48:07.950Z
Answers.LastActivityDate: 2019-12-11T11:48:07.950Z
Answers.UserDisplayName: Arnav Gupta
Body: <p>How does a transformer leverage the GPU to be trained faster than RNNs?</p>
  <p>I understand the parameter space of the transformer might be significantly larger than that of the RNN. But why does the transformer structure can leverage multiple GPUs, and why does that accelerate its training?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-11-30T23:06:22.750Z
Comments.Text: A recurrent network depends on the previous time steps hidden state. Therefore you can’t calculate the $t$th hidden state without first calculating the $t-1$th. This is not the case with transformers, there is no such recursive dependency — the recursive nature is capture in other ways (eg through self attention and explicitly positional encoding)
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-12-01T12:22:57.887Z
Comments.Text: @DavidIreland That seems like a good starting point for a formal answer.
Comments.UserDisplayName: nbro
Tags: <natural-language-processing><training><transformer><attention><gpu>
Title: How does a transformer leverage the GPU to be trained faster than RNNs?
UserDisplayName: YoYO Man
ThreadText: # How does a transformer leverage the GPU to be trained faster than RNNs?
  
  (Asked by: username_0 on 2019-12-10)
  
  How does a transformer leverage the GPU to be trained faster than RNNs?
  
  I understand the parameter space of the transformer might be significantly larger than that of the RNN. But why does the transformer structure can leverage multiple GPUs, and why does that accelerate its training?
  
  **Tags:** natural-language-processing, training, transformer, attention, gpu
  
  > **Comments:**
  > **username_1**: A recurrent network depends on the previous time steps hidden state. Therefore you can’t calculate the $t$th hidden state without first calculating the $t-1$th. This is not the case with transformers, there is no such recursive dependency — the recursive nature is capture in other ways (eg through self attention and explicitly positional encoding)  
  > **username_2**: @DavidIreland That seems like a good starting point for a formal answer.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2021-12-02. Score: 2
  
  A recurrent neural network (RNN) depends on the previous hidden state from the previous time step. That is, an RNN is a function of both the data for the sequence at time $t$ and the hidden state from time $t-1$. This means that we cannot compute the $t$th hidden state without calculating the $t-1$th state, and the $t-1$th state without the $t-2$th state, and so on.
  
  In contrast to this, a transformer is able to fully parallelise the processing of the sequence because it does not have this recursive relationship, i.e. a transformer is not a recursive function -- the recursive nature of the sequence is processed in other ways, such as through positional encoding. We can see this by the way self attention works.
  
  If we first consider the general attention mechanism framework, then we have a query $q$ and a set of paired key-value tuples $\textbf{k}\_1, ..., \textbf{k}\_n$ and $\textbf{v}\_1, ..., \textbf{v}\_n$. In general, for each key, we will apply some attention function $\beta$ (such as a neural network) to obtain attention scores, $a\_i = \beta(\textbf{q}, \textbf{k}\_i)$. We then define an attention vector $\textbf{a}$ where the $i$th element is the $i$th attention score, and we take a softmax of this vector to obtain attention weights $\alpha\_i$ where $\alpha\_i$ is the $i$th element of $\mbox{softmax}(\textbf{a})$. The output of the attention mechanism for query $\textbf{q}$ is then the weighted sum $\sum\_{i=1}^n \alpha\_i \textbf{v}\_i$.
  
  Now that we have the necessary background for an attention mechanism, we can look at self attention which is the backbone of Transformer. If we have a sequence denoted by $\{\textbf{x}\_1, ..., \textbf{x}\_n\}$, then we can define a set of queries, keys and values to be these $\textbf{x}\_i$ values. Note that previously we only had a single query, but here we will have multiple queries which is really how Transformer is able to parallelise the processing of the sequence. If we define $\textbf{Q}, \textbf{K}, \textbf{V}$ to be the matrices of the queries, keys and values (e.g. the $i$th row of $\textbf{Q}$ corresponds to the $i$th query, and similarly for the others). Self attention is as simple as performing attention over these query, key and values -- the name *self* comes from the fact that the queries, keys and values are all the same and represent the $i$th element of the sequence. Now, we can write the above attention mechanism as $a\_{i, j} = \beta(Q, K)$ where we now have a matrix of attention scores (because we have $i$ queries and $i$ keys the matrix will be square), and we can take softmax row-wise to get the attention weights (again, this will be an $i\times i$ matrix). If we call the matrix of attention weights $\textbf{A}$ then the output of a self attention layer will be given by $\textbf{A} \textbf{V}$. As you can see, there is no recursive nature here and this is all parallelisable, e.g. it can be broken up and put onto multiple GPU's at the same time -- this would not be possible with an RNN as you would have to wait for the output of the previous layer.
  
  > **Comments:**
  > **username_1**: please someone let me know if I have messed up the orders of my matrix multiplications.  
  > **username_1**: @abcd kind of, yes. The RNN has access to information from previous time steps through the hidden state, but if you look at how this is updated (in e.g. LSTMs which use a gating mechanism) then it starts to lose more information about time $t$ at time $t+k$ as $k$ increases. This isn't wholly true in transformers, as they attend to every previous token in the context window.  
  > **username_1**: I'm less sure on them but I think the same problem would happen. For really long sequences, the hidden state would start to lose information (I think).  
  > **username_1**: @abcd kind of hard to answer in a comment, probably it would require a writing out of the equations used in attention (perhaps you could ask it in a question and either myself or someone else will answer it), but basically if you look at how self-attention works, you can see that they attend to every token in the sequence without any loss of information (e.g. there is no attempt to collect all prior information in a single dynamic state)  
  
  ---
  
  ### Answer by username_3 on 2019-12-11. Score: 0
  
  The issue with Recurrent models is that they don't parallelization during training.
  Sequential models performs better with more memory but faces problem in learning long-term memory dependencies.
  
  On the other hand Transformers take into account of **self attention** which boosts the speed of how fast the model can translate from one sequence to another and establishes dependencies b/w input and output and focus on relevant parts of the input sequence, which in turn eliminates recurrence and convolution unlike RNNs where sequential computation inhibits parallelization.
  
  > **Comments:**
  > **username_2**: This answer does not provide much insight into how transformers are "more parallelizable" than RNNs. You say "unlike RNNs where sequential computation inhibits parallelization", but that's not very useful because you don't explain why transformers avoid the issue and why "sequential computation" is really the problem. You talk about many things that are irrelevant to answer the question and only give a few words to answer the question, which are unclear.  
  
  ---
  
  