Answers.Body: <p>They don't seem to be sharing any supplementary material with details on this, however as they state, convolution being independent from the input size can be applied to varying size input (see WaveNet for example)</p>
  <p>The sequential  part is trivial, as it has no sequential notion the convolution (apart from animations). For the last column, refer to the paper, they explain  at the end of Section 4. Regarding the first one, it's the usual <a href="https://scicomp.stackexchange.com/questions/10356/computational-complexity-of-2d-convolution">complexity of a convolution</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-21T22:13:17.053Z
Answers.LastActivityDate: 2024-04-21T22:13:17.053Z
Answers.UserDisplayName: Alberto
Body: <p><a href="https://i.sstatic.net/gwwKfw5I.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/gwwKfw5I.png" alt="enter image description here" /></a></p>
  <p>In the paper <a href="https://arxiv.org/abs/1706.03762" rel="nofollow noreferrer">Attention is all you need</a>, here is Table 1, can someone explain what architecture is referred to in the &quot;Convolution&quot; row and hence describe the other 3 columns in it? The other ones are pretty clear, for example Recurrent, takes <span class="math-container">$O(d^2)$</span> operations in one time-step to multiply the hidden state with the weight matrix, and there are <span class="math-container">$n$</span> such time-steps, which need to be done sequentially (<span class="math-container">$O(n)$</span>), also making the information from the first and last tokens in the sentence to travel <span class="math-container">$O(n)$</span> steps. For Self-attention, every word in the sentence, attends to every other, so <span class="math-container">$O(n^2)$</span> pairs, dot product attention taking <span class="math-container">$O(d)$</span> operations. Clearly, the path length is <span class="math-container">$O(1)$</span> and there are no sequential operation, all these <span class="math-container">$O(n^2)$</span> pairs can be computed independently. The &quot;Convolution&quot; row is not clear to me!</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-04-22T13:24:08.313Z
Comments.Text: Can you please put your **specific** question in the title? "CNN's for NLP, Attention is all you need" is not a question and it's also not your question
Comments.UserDisplayName: nbro
Tags: <deep-learning><convolutional-neural-networks><transformer><attention>
Title: How to get Complexity per Layer, Sequential Operations and Maximum Path Length in CNN architecture?
UserDisplayName: Harry
ThreadText: # How to get Complexity per Layer, Sequential Operations and Maximum Path Length in CNN architecture?
  
  (Asked by: username_0 on 2024-04-21)
  
  [![enter image description here](https://i.sstatic.net/gwwKfw5I.png)](https://i.sstatic.net/gwwKfw5I.png)
  
  In the paper [Attention is all you need](https://arxiv.org/abs/1706.03762), here is Table 1, can someone explain what architecture is referred to in the "Convolution" row and hence describe the other 3 columns in it? The other ones are pretty clear, for example Recurrent, takes $O(d^2)$ operations in one time-step to multiply the hidden state with the weight matrix, and there are $n$ such time-steps, which need to be done sequentially ($O(n)$), also making the information from the first and last tokens in the sentence to travel $O(n)$ steps. For Self-attention, every word in the sentence, attends to every other, so $O(n^2)$ pairs, dot product attention taking $O(d)$ operations. Clearly, the path length is $O(1)$ and there are no sequential operation, all these $O(n^2)$ pairs can be computed independently. The "Convolution" row is not clear to me!
  
  **Tags:** deep-learning, convolutional-neural-networks, transformer, attention
  > **Comments:**
  > **username_1**: Can you please put your **specific** question in the title? "CNN's for NLP, Attention is all you need" is not a question and it's also not your question  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2024-04-21. Score: 0
  
  They don't seem to be sharing any supplementary material with details on this, however as they state, convolution being independent from the input size can be applied to varying size input (see WaveNet for example)
  
  The sequential part is trivial, as it has no sequential notion the convolution (apart from animations). For the last column, refer to the paper, they explain at the end of Section 4. Regarding the first one, it's the usual [complexity of a convolution](https://scicomp.stackexchange.com/questions/10356/computational-complexity-of-2d-convolution)
  
  
  ---
  
  