Self-attention layers exhibit a per-layer computational complexity of $O(n^2 \cdot d)$ and execute in $O(1)$ sequential operations. In contrast, standard recurrent layers require $O(n \cdot d^2)$ operations per layer and $O(n)$ sequential operations, because hidden states $h_t$ must be computed sequentially from $h_{t-1}$.

In machine translation and natural language processing tasks using word-piece or byte-pair representations, the sequence length $n$ is typically smaller than the representation dimensionality $d$. Consequently, self-attention layers are computationally faster than recurrent layers in practice, while fully enabling parallel computation across all positions within a training example.

To improve computational efficiency for tasks involving very long sequences where $n$ is large, self-attention can be restricted to attend only to a neighborhood of size $r$ centered around the respective output position. This restricted self-attention reduces the per-layer complexity to $O(r \cdot n \cdot d)$ while keeping sequential operations at $O(1)$.