Answers.Body: <p>The additive attention method that the researchers are comparing to corresponds to a neural network with 3 layers (it is not actually straight addition). Computing this will involve one multiplication of the input vector by a matrix, then by another matrix, and then the computation of something like a softmax. Smart implementation of a dot-product will not break out the whole matrix multiplication algorithm for it, and it will basically be a tight, easily parallelized loop.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-18T16:41:01.203Z
Answers.Text: Do you have a source for the 3 layer structure? If you see the chart comparing attentions here: https://lilianweng.github.io/lil-log/2018/06/24/attention-attention.html
Answers.UserDisplayName: user3180
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-18T16:41:36.443Z
Answers.Text: Lilian says the only difference between additive and dot product is Q + K vs Q K^T. I don't see any mention of multiple layers to compute Q + K
Answers.UserDisplayName: user3180
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-18T20:21:57.053Z
Answers.Text: @user3180 I think it's right in the quote in your question. " Additive attention computes the compatibility function using a feed-forward network with
  a single hidden layer. " A single hidden layer means it's a 3 layer network (input + hidden + output)
Answers.UserDisplayName: John Doucette
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-18T21:50:17.857Z
Answers.Text: That line still doesn't make sense to me. Looking at a reputable implementation of additive attention, they literally just sum the Q + K tensors. Are you implying the network takes in Q concatenated with K, passes through the MLP, to get Q + K? It does not make much sense to call that concatenation + MLP operation as "addition"
Answers.UserDisplayName: user3180
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-09-23T00:46:30.627Z
Answers.Text: Just think about the parameterizations that lead to Q and K. If they are obtained by some transformations such as Q=f(x; W_Q), K=f(x; W_K), there will be no need to apply additional transformations like Q=f(x; W_Q, A_Q), K=f(x; W_K, A_K).
Answers.UserDisplayName: Jiang Xiang
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-18T04:00:34.207Z
Answers.LastActivityDate: 2021-01-06T23:38:49.820Z
Answers.LastEditDate: 2021-01-06T23:38:49.820Z
Answers.UserDisplayName: John Doucette
Answers.Body: <p>Two are similar in theoretical complexity.</p>
  <p>But matrix multiplication is better optimized. According to <a href="https://arxiv.org/pdf/2007.00072.pdf" rel="nofollow noreferrer">this paper</a>, non-matmul ops in transformer are 15x slower than matmul operation.</p>
  <p><img src="https://horace.io/img/perf_intro/bert_flops.png" alt="" /></p>
  <p><a href="https://horace.io/brrr_intro.html" rel="nofollow noreferrer">Making Deep Learning Go Brrrr From First Principles</a> discuses about similar topics.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-03-18T08:40:10.500Z
Answers.LastActivityDate: 2022-03-18T08:40:10.500Z
Answers.UserDisplayName: Eric
Answers.Body: <p>In additive attention (as described in <a href="https://arxiv.org/abs/1409.0473" rel="nofollow noreferrer">the paper by Bahdanau et al. (2014)</a>), the alignment model <span class="math-container">$a$</span> is represented by a feedforward neural network. If you look in their appendix, they actually implement this as</p>
  <p><span class="math-container">$$ e_{ij} = V_a^T \tanh \left(W_a s_{i-1} + U_a h_j\right) = V_a^T \tanh \left(Q + K\right).$$</span></p>
  <p>In contrast, in dot-product attention (as described in <a href="https://arxiv.org/abs/1706.03762" rel="nofollow noreferrer">the paper by Vaswani et al. (2017)</a>), the alignment model is implemented as</p>
  <p><span class="math-container">$$ e_{ij} = W_Q s_{i-1} \left(W_K h_j\right)^T = Q K^T.$$</span></p>
  <p>The computational advantage is that the dot-product alignment model has only two weight matrices and only needs matrix multiplication, for which highly-optimized code exists.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-09-07T07:33:22.737Z
Answers.LastActivityDate: 2021-09-07T07:38:32.757Z
Answers.LastEditDate: 2021-09-07T07:38:32.757Z
Answers.UserDisplayName: Felix Kemeth
Body: <p>In section 3.2.1 of <a href="https://arxiv.org/pdf/1706.03762.pdf" rel="noreferrer">Attention Is All You Need</a> the claim is made that:</p>
  
  <blockquote>
    <p>Dot-product attention is identical to our algorithm, except for the scaling factor of <span class="math-container">$\frac{1}{\sqrt{d_k}}$</span>. Additive attention computes the compatibility function using a feed-forward network with a single hidden layer. While the two are similar in theoretical complexity, dot-product attention is much faster and more space-efficient in practice, since it can be implemented using highly optimized matrix multiplication code.</p>
  </blockquote>
  
  <p>It does not make sense why dot product attention would be faster. Additive attention is nearly identical computation wise; the main difference is <span class="math-container">$Q + K$</span> instead of <span class="math-container">$Q K^T$</span> in dot product attention. <span class="math-container">$Q K^T$</span> requires at least as many addition operations as <span class="math-container">$Q + K$</span>, so how can it possibly be faster?</p>
  
Tags: <neural-networks><machine-learning><deep-learning><attention>
Title: Why is dot product attention faster than additive attention?
UserDisplayName: user3180
ThreadText: # Why is dot product attention faster than additive attention?
  
  (Asked by: username_0 on 2019-04-17)
  
  In section 3.2.1 of [Attention Is All You Need](https://arxiv.org/pdf/1706.03762.pdf) the claim is made that:
  
  > Dot-product attention is identical to our algorithm, except for the scaling factor of $\frac{1}{\sqrt{d\_k}}$. Additive attention computes the compatibility function using a feed-forward network with a single hidden layer. While the two are similar in theoretical complexity, dot-product attention is much faster and more space-efficient in practice, since it can be implemented using highly optimized matrix multiplication code.
  
  It does not make sense why dot product attention would be faster. Additive attention is nearly identical computation wise; the main difference is $Q + K$ instead of $Q K^T$ in dot product attention. $Q K^T$ requires at least as many addition operations as $Q + K$, so how can it possibly be faster?
  
  **Tags:** neural-networks, machine-learning, deep-learning, attention
  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_1 on 2019-04-18. Score: 3
  
  The additive attention method that the researchers are comparing to corresponds to a neural network with 3 layers (it is not actually straight addition). Computing this will involve one multiplication of the input vector by a matrix, then by another matrix, and then the computation of something like a softmax. Smart implementation of a dot-product will not break out the whole matrix multiplication algorithm for it, and it will basically be a tight, easily parallelized loop.
  
  > **Comments:**
  > **username_0**: Do you have a source for the 3 layer structure? If you see the chart comparing attentions here: https://lilianweng.github.io/lil-log/2018/06/24/attention-attention.html  
  > **username_0**: Lilian says the only difference between additive and dot product is Q + K vs Q K^T. I don't see any mention of multiple layers to compute Q + K  
  > **username_1**: @username_0 I think it's right in the quote in your question. " Additive attention computes the compatibility function using a feed-forward network with a single hidden layer. " A single hidden layer means it's a 3 layer network (input + hidden + output)  
  > **username_0**: That line still doesn't make sense to me. Looking at a reputable implementation of additive attention, they literally just sum the Q + K tensors. Are you implying the network takes in Q concatenated with K, passes through the MLP, to get Q + K? It does not make much sense to call that concatenation + MLP operation as "addition"  
  > **username_2**: Just think about the parameterizations that lead to Q and K. If they are obtained by some transformations such as Q=f(x; W_Q), K=f(x; W_K), there will be no need to apply additional transformations like Q=f(x; W_Q, A_Q), K=f(x; W_K, A_K).  
  
  ---
  
  ### Answer by username_3 on 2022-03-18. Score: 2
  
  Two are similar in theoretical complexity.
  
  But matrix multiplication is better optimized. According to [this paper](https://arxiv.org/pdf/2007.00072.pdf), non-matmul ops in transformer are 15x slower than matmul operation.
  
  ![](https://horace.io/img/perf_intro/bert_flops.png)
  
  [Making Deep Learning Go Brrrr From First Principles](https://horace.io/brrr_intro.html) discuses about similar topics.
  
  
  ---
  
  ### Answer by username_4 on 2021-09-07. Score: 2
  
  In additive attention (as described in [the paper by Bahdanau et al. (2014)](https://arxiv.org/abs/1409.0473)), the alignment model $a$ is represented by a feedforward neural network. If you look in their appendix, they actually implement this as
  
  $$ e\_{ij} = V\_a^T \tanh \left(W\_a s\_{i-1} + U\_a h\_j\right) = V\_a^T \tanh \left(Q + K\right).$$
  
  In contrast, in dot-product attention (as described in [the paper by Vaswani et al. (2017)](https://arxiv.org/abs/1706.03762)), the alignment model is implemented as
  
  $$ e\_{ij} = W\_Q s\_{i-1} \left(W\_K h\_j\right)^T = Q K^T.$$
  
  The computational advantage is that the dot-product alignment model has only two weight matrices and only needs matrix multiplication, for which highly-optimized code exists.
  
  
  ---
  
  