Attention Is All You Need

4 Why Self-Attention

1. Compare self-attention, recurrent and convolutional layers by complexity, sequential operations and maximum path length.
   Per-layer cost, minimum sequential operations (seq.) and maximum path length between positions (\(n\) = sequence length, \(d\) = dimension, \(k\) = kernel width):

   layer	cost	seq.	path
   self-attn.	\(O(n^2 d)\)	\(O(1)\)	\(O(1)\)
   recurrent	\(O(n d^2)\)	\(O(n)\)	\(O(n)\)
   convol.	\(O(k n d^2)\)	\(O(1)\)	\(O(\log_k n)\)

   • Vaswani et al., 2017, Attention Is All You Need (Advances in Neural Information Processing Systems 30 (NIPS 2017)), §4
2. When is self-attention cheaper than a recurrent layer, and what about very long sequences?
   When sequence length \(n\) is smaller than dimension \(d\), usually the case for sentences with word-piece or BPE tokens. For very long sequences, attention could be restricted to a neighbourhood of size \(r\), raising the maximum path length to \(O(n/r)\).
   • Vaswani et al., 2017, Attention Is All You Need (Advances in Neural Information Processing Systems 30 (NIPS 2017)), §4
3. Why do short paths between positions matter?
   Learning long-range dependencies is a key challenge, and the shorter the paths forward and backward signals must traverse between any input and output positions, the easier such dependencies are to learn. Self-attention connects all positions in a constant number of steps.
   • Vaswani et al., 2017, Attention Is All You Need (Advances in Neural Information Processing Systems 30 (NIPS 2017)), §4