Study the paper

Attention Is All You Need

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

Comparing Self-Attention with Recurrence and Convolution

Comparing Self-Attention, Recurrent, and Convolutional Layers

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)

To understand why self-attention is highly efficient, we can compare its computational complexity, sequential operations, and maximum path lengths against recurrent and convolutional layers. The maximum path length measures the maximum number of steps a signal must travel to connect any two positions in the network, which impacts the model's ability to learn long-range dependencies.

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)

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.

Implementation detail

| Layer Type | Complexity per Layer | Sequential Operations | Maximum Path Length | | :--- | :--- | :--- | :--- | | Self-Attention | $O(n^2 \cdot d)$ | $O(1)$ | $O(1)$ | | Recurrent | $O(n \cdot d^2)$ | $O(n)$ | $O(n)$ | | Convolutional | $O(k \cdot n \cdot d^2)$ | $O(1)$ | $O(\log_k(n))$ | | Self-Attention (restricted) | $O(r \cdot n \cdot d)$ | $O(1)$ | $O(n/r)$ |

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

As shown in the table, self-attention layers connect all positions with a constant $O(1)$ number of sequentially executed operations, whereas recurrent layers require $O(n)$ sequential operations. When the sequence length $n$ is smaller than the representation dimension $d$ (which is typical for sentence representations in machine translation), self-attention layers are computationally faster than recurrent layers.

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.