Study the paper

Attention Is All You Need

Lessons, visuals, quizzes, flashcards, and resources—organized in teaching order.

Comparing Self-Attention, Recurrent, and Convolutional Layers

Computational Complexity of Layer Types

To understand the computational advantages of self-attention, we compare its per-layer complexity, sequential operations, and maximum path length against recurrent and convolutional layers. Let $n$ be the sequence length and $d$ be the representation dimension.

Sources

S4.T1

Table 1: Maximum path lengths, per-layer complexity and minimum number of sequential operations for different layer types. nn is the sequence length, dd is the representation dimension, kk is the kernel size of convolutions and rr the size of the neighborhood in restricted self-attention. Layer Type Complexity per Layer Sequential Maximum Path Length Operations Self-Attention O(n2⋅d)O(n^{2}\cdot d) O(1)O(1) O(1)O(1) Recurrent O(n⋅d2)O(n\cdot d^{2}) O(n)O(n) O(n)O(n) Convolutional O(k⋅n⋅d2)O(k\cdot n\cdot d^{2}) O(1)O(1) O(logk(n))O(log_{k}(n)) Self-Attention (restricted) O(r⋅n⋅d)O(r\cdot n\cdot d) O(1)O(1) O(n/r)O(n/r)

Self-Attention: Complexity per layer is $O(n^2 \cdot d)$ , sequential operations are $O(1)$ , and the maximum path length is $O(1)$ .
Recurrent: Complexity per layer is $O(n \cdot d^2)$ , sequential operations are $O(n)$ , and the maximum path length is $O(n)$ .
Convolutional: Complexity per layer is $O(k \cdot n \cdot d^2)$ (where $k$ is kernel size), sequential operations are $O(1)$ , and the maximum path length is $O(\log_k(n))$ .

Sources

S4.T1

Table 1: Maximum path lengths, per-layer complexity and minimum number of sequential operations for different layer types. nn is the sequence length, dd is the representation dimension, kk is the kernel size of convolutions and rr the size of the neighborhood in restricted self-attention. Layer Type Complexity per Layer Sequential Maximum Path Length Operations Self-Attention O(n2⋅d)O(n^{2}\cdot d) O(1)O(1) O(1)O(1) Recurrent O(n⋅d2)O(n\cdot d^{2}) O(n)O(n) O(n)O(n) Convolutional O(k⋅n⋅d2)O(k\cdot n\cdot d^{2}) O(1)O(1) O(logk(n))O(log_{k}(n)) Self-Attention (restricted) O(r⋅n⋅d)O(r\cdot n\cdot d) O(1)O(1) O(n/r)O(n/r)

Deep dive

Self-attention layers are computationally faster than recurrent layers when the sequence length $n$ is smaller than the representation dimension $d$ . This is typically the case for sentence representations used in state-of-the-art machine translation models.

Sources

S4.p4.5

As noted in Table 1, a self-attention layer connects all positions with a constant number of sequentially executed operations, whereas a recurrent layer requires O(n)O(n) sequential operations. In terms of computational complexity, self-attention layers are faster than recurrent layers when the sequence length nn is smaller than the representation dimensionality dd, which is most often the case with sentence representations used by state-of-the-art models in machine translations, such as word-piece [38] and byte-pair [31] representations. To improve computational performance for tasks involving very long sequences, self-attention could be restricted to considering only a neighborhood of size rr in the input sequence centered around the respective output position. This would increase the maximum path length to O(n/r)O(n/r). We plan to investigate this approach further in future work.