A critical factor governing a model's ability to learn long-range dependencies is the maximum path length signals must traverse between arbitrary input and output positions in the network. Shorter paths preserve gradient flow and make dependency learning easier.

Self-attention directly connects every position to every other position, resulting in a constant maximum path length of $O(1)$. Recurrent architectures, by processing sequences sequentially step-by-step, require a maximum path length of $O(n)$.

Convolutional layers with kernel width $k < n$ cannot connect all pairs of input and output positions in a single layer. Connecting all positions requires a stack of $O(n/k)$ convolutional layers for contiguous kernels, or $O(\log_k(n))$ layers in the case of dilated convolutions, yielding maximum path lengths of $O(n/k)$ and $O(\log_k(n))$, respectively. If restricted self-attention over a neighborhood $r$ is utilized instead of full self-attention, the maximum path length increases to $O(n/r)$.