Transformer-XL (2019) › The Problem

Full self-attention over $n$ tokens forms an $n \times n$ score matrix, so its time and memory costs grow as $O(n^2)$. Training on an entire long document was therefore expensive. Splitting the document into length-$L$ segments controlled the cost but restricted each prediction to its current segment.

This restriction also wasted computation at evaluation time. To predict one segment with a longer history, a vanilla model had to process that history again. Moving the window forward repeated many of the same layer calculations.

Absolute position encodings caused a second problem once hidden states were reused. A cached state already contained the absolute index it had in the old segment. When attached before a new segment, the same state needed to be interpreted at a different distance from each new query. Reusing it without changing the attention formulation produced a positional mismatch.

Transformer-XL addressed these two issues together. Recurrence reused the old activations; relative attention described where a cached key sat with respect to the current query.