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

Analyzing Computational Complexity and Path Lengths

Self-attention layers connect all positions with a constant number of sequentially executed operations ( $O(1)$ ), whereas recurrent layers require $O(n)$ sequential operations. In terms of computational complexity, self-attention layers are faster than recurrent layers when the sequence length $n$ is smaller than the representation dimensionality $d$ , which is typical for state-of-the-art machine translation models.

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.

Deep dive

A single convolutional layer with kernel width $k < n$ does not connect all pairs of input and output positions. Doing so requires a stack of $O(n/k)$ convolutional layers (for contiguous kernels) or $O(\log_k(n))$ (for dilated convolutions), which increases the maximum path length between positions in the network.

Sources

S4.p5.6

A single convolutional layer with kernel width k<nk<n does not connect all pairs of input and output positions. Doing so requires a stack of O(n/k)O(n/k) convolutional layers in the case of contiguous kernels, or O(logk(n))O(log_{k}(n)) in the case of dilated convolutions [18], increasing the length of the longest paths between any two positions in the network. Convolutional layers are generally more expensive than recurrent layers, by a factor of kk. Separable convolutions [6], however, decrease the complexity considerably, to O(k⋅n⋅d+n⋅d2)O(k\cdot n\cdot d+n\cdot d^{2}). Even with k=nk=n, however, the complexity of a separable convolution is equal to the combination of a self-attention layer and a point-wise feed-forward layer, the approach we take in our model.