<p>You cannot compare this to a traditional RNN encoder-decoder, the architecture described in the paper is meant to improve upon the classical <code>Attention Mechanism</code> first established in this <a href="https://arxiv.org/pdf/1409.0473.pdf" rel="nofollow noreferrer">paper</a>.</p>
<p>In its initial form, the attention mechanism was relying on a Neural network trained to retrieved the relevant hidden states of the encoder. Instead of relying on a fixed retrieval strategy (for instance: using the last hidden state) you allow the system some control over the process.</p>
<p><a href="https://i.stack.imgur.com/aW7nJ.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/aW7nJ.png" alt="enter image description here" /></a></p>
<p>There is already a very good post on StackExchange explaining the differences in computational complexity <a href="https://stats.stackexchange.com/questions/421935/what-exactly-are-keys-queries-and-values-in-attention-mechanisms">here</a>.</p>
<p>The paper you are describing is &quot;replacing&quot; this Neural Network with a dot product between two array, which less demanding computationally than having to train a Neural Network and relatively more efficient. But its not meant to be more efficient than a regular RRN-based auto-encoder without attention.</p>
<blockquote>
<p>How is this any less demanding computationally?</p>
</blockquote>
<p>In a traditionnal RNN / LSTM based auto encoder each time step is encoded into a vector <code>h</code>. The decoder usually (again, there's a lot of different architectures but that's the basic one) takes the last vector <code>h</code> as input produce the output sequence.</p>
<p><a href="https://i.stack.imgur.com/GxX0N.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/GxX0N.png" alt="enter image description here" /></a></p>
<p>In this scenario there are no attention mechanism, this is straight forward reading the last encoded state.
The problem with this architecture is that as your sequence gets longer, all the relevant information gets squeezed into the last encoded state <code>h(t)</code> and you loose relevant information.</p>
<p><strong>Introducing attention mechanism</strong></p>
<p>As described in the paper above, the original attention mechanism aims at circumventing this limitation by allowing the decoder to access not only the last encoded state but any of the previous encoded state and to combine them in order to improve on the prediction.</p>
<p>For each time steps, a probability vector <code>alpha</code> is computed by a neural network to choose encoded state to retreive :</p>
<blockquote>
<p>If we restrict α to be an one-hot vector, this operation becomes the same as retrieving from a set of elements h with index α. With the restriction removed, the attention operation can be thought of as doing &quot;proportional retrieval&quot; according to the probability vector α</p>
</blockquote>
<p>I won't copy paste the SE <a href="https://stats.stackexchange.com/questions/421935/what-exactly-are-keys-queries-and-values-in-attention-mechanisms">post</a> , there you'll have the explanation on why the method of the dot product is computationally more efficient than the neural network.</p>
<p><strong>Conclusion</strong></p>
<p>The key take away is that you cannot compare this to a traditional RNN encoder-decoder because there are no <code>attention mechanism</code> in such network. It would be like comparing CNN with LSTM layer, these are just different architecture.</p>
Computational Complexity of Self-Attention in the Transformer Model
<p>I recently went through the <a href="https://papers.nips.cc/paper/2017/file/3f5ee243547dee91fbd053c1c4a845aa-Paper.pdf" rel="noreferrer">Transformer</a> paper from Google Research describing how self-attention layers could completely replace traditional RNN-based sequence encoding layers for machine translation. In Table 1 of the paper, the authors compare the computational complexities of different sequence encoding layers, and state (later on) that self-attention layers are faster than RNN layers when the sequence length <code>n</code> is smaller than the dimensionality of the vector representations <code>d</code>.</p>
<p>However, the self-attention layer seems to have an inferior complexity than claimed if my understanding of the computations is correct. Let <code>X</code> be the input to a self-attention layer. Then, <code>X</code> will have shape <code>(n, d)</code> since there are <code>n</code> word-vectors (corresponding to rows) each of dimension <code>d</code>. Computing the output of self-attention requires the following steps (consider single-headed self-attention for simplicity):</p>
<ol>
<li>Linearly transforming the rows of <code>X</code> to compute the query <code>Q</code>, key <code>K</code>, and value <code>V</code> matrices, each of which has shape <code>(n, d)</code>. This is accomplished by post-multiplying <code>X</code> with 3 learned matrices of shape <code>(d, d)</code>, amounting to a computational complexity of <code>O(n d^2)</code>.</li>
<li>Computing the layer output, specified in Equation 1 of the paper as <code>SoftMax(Q Kt / sqrt(d)) V</code>, where the softmax is computed over each row. Computing <code>Q Kt</code> has complexity <code>O(n^2 d)</code>, and post-multiplying the resultant with <code>V</code> has complexity <code>O(n^2 d)</code> as well.</li>
</ol>
<p>Therefore, the total complexity of the layer is <code>O(n^2 d + n d^2)</code>, which is worse than that of a traditional RNN layer. I obtained the same result for multi-headed attention too, on considering the appropriate intermediate representation dimensionalities (<code>dk</code>, <code>dv</code>) and finally multiplying by the number of heads <code>h</code>.</p>
<p>Why have the authors ignored the cost of computing the Query, Key, and Value matrices while reporting total computational complexity?</p>
<p>I understand that the proposed layer is fully parallelizable across the <code>n</code> positions, but I believe that Table 1 does not take this into account anyway.</p>