Transformer-XL,
explained.

Rung 1, so the comparison is against how a plain transformer is trained on long text: chop it into fixed-length segments and treat each as an independent example. That has a consequence worse than a short window, and naming it is this rung's first contribution. A token near the start of a segment has almost no context at all — not a truncated history, but a history that was arbitrarily severed at a position determined by where the chopping happened to fall. The model is trained on a large number of examples that begin mid-sentence with no past.

The change is to cache the hidden states of the previous segment and let the current segment attend to them, without propagating gradients back into the cache. Each layer can therefore reach one segment further back than the layer below it, so the effective context grows with depth rather than being fixed by the window — a deep model sees far more than one segment even though no single attention operation spans more than two.

That immediately forces a second change, and it is the one with the longer legacy. With a cache in play, absolute positions collide: the first token of the cached segment and the first token of the current segment both want to be position zero, and the model cannot tell them apart. So positions have to be encoded as relative offsets between the query and the key rather than as absolute indices — a requirement discovered here as a consequence of recurrence, not as an aesthetic preference. The other reported gain is practical and large: evaluating a long document no longer requires re-encoding an overlapping window for every single token, which speeds inference up by a wide margin.

A standard transformer attends over a fixed-length window — a segment of, say, 512 tokens. To process a long document you chop it into segments and run each one independently. That creates two problems. First, the model can never learn a dependency longer than one segment, because information never crosses a boundary — the paper calls this context fragmentation. Second, at evaluation time, to predict each new token you slide the window forward by one and recompute the whole segment from scratch, which is enormously wasteful.

Both problems come from the same root: each segment is an island. Transformer-XL's fix is to build bridges between the islands — let a segment see the one before it — without paying to reprocess the past. Two mechanisms make that work, and they turn out to depend on each other.

The first mechanism is segment-level recurrence. When processing a segment, Transformer-XL caches the hidden states it produced for the previous segment, at every layer. The current segment's attention can then read from its own tokens and from those cached states — extending its view one segment into the past. The cache is treated as fixed input (stop-gradient: no backpropagation flows into it), so training stays cheap.

The elegance is how this compounds with depth. Layer 1 of the current segment reaches back into layer 1 of the previous segment. But layer 2 reads layer-1 states that already incorporated the segment before that. So each additional layer extends the reach by roughly another segment — the effective context grows about linearly with the number of layers, not staying pinned at a single segment length. A 12-layer model with 512-token segments can carry information across thousands of tokens.

Recurrence breaks something. The original transformer adds an absolute position embedding — position 0, 1, 2, … within the segment. But with recurrence, the same absolute indices reappear in every segment: the cached previous segment also has a "position 3." Add absolute embeddings and two tokens from different segments look identically placed; the model can't tell the recent "position 3" from the older one. Recurrence and absolute positions are incompatible.

The fix is relative positional encoding: encode the distance between a query and a key, not their absolute indices. Distance is well-defined across segment boundaries — a token 5 steps back is 5 steps back whether it's in this segment or the last:

Because rel(5,3) = rel(105,103) = 2, the encoding is identical no matter where in the stream the pair sits — exactly the property recurrence needs. Transformer-XL folds this relative distance directly into the attention score computation. The runnable version below confirms the shift-invariance and the context growth.

Recurrence pays a second dividend at inference. A vanilla transformer, generating token by token, slides its fixed window forward one step at a time and recomputes the entire context for each new token — order L work per token for a segment length L. Transformer-XL already has the previous segment's states cached, so it processes a new segment once and reuses the cache — no re-computation of the past.

So the same cache that extends the context also removes the redundant recomputation that made long-context evaluation painfully slow. Longer reach and faster inference from one idea — carry the past forward instead of rebuilding it.

Transformer-XL, from Dai, Yang, Yang, Carbonell, Le and Salakhutdinov, is a decoder-only language model that reads a long text as a sequence of fixed-length segments, in order, carrying a memory of hidden states from one segment to the next. Two mechanisms do the work, and the second exists because of the first.

1. Keep segments in order. Training reads consecutive segments of length L from the same text stream instead of independent, shuffled windows, so every segment has a real predecessor whose states can be reused.
2. Cache every layer's hidden states. After segment τ is processed, its hidden states at every layer are kept as memory. A stop-gradient sits on that memory: it is read as a fixed input, and backpropagation stays inside the current segment.
3. Extend keys and values, never queries. For layer n of segment τ+1, the cached layer-(n−1) states of segment τ are concatenated in front of the current layer-(n−1) states. Queries come only from the current segment; keys and values come from the concatenation, under a causal mask. Each current token therefore attends to its own segment plus M cached positions.
4. Score with relative positions. No absolute position embedding is added to the input. The attention score between query i and key j is the sum of four terms: content against content, content against a sinusoidal encoding of the distance i − j, and two learned global bias vectors, u and v, that take the query's place in a content-only term and a distance-only term. Content and distance get separate key projections.
5. Compute the distance term efficiently. Naively every query-key pair needs its own distance vector. The paper computes the distance term once against all possible distances and shifts each row into place, so the cost stays that of ordinary attention.
6. Let depth compound the reach. Layer n of segment τ+1 reads layer n−1 of segment τ, which had already read layer n−2 of segment τ−1. The longest dependency therefore grows roughly with the number of layers times the segment length, O(N × L), although each attention step spans only two segments.
7. Evaluate with a longer memory. Because positions are relative, the memory can be much longer at test time than during training. Evaluation processes a whole segment at once and reuses the cache, instead of sliding a window forward one token at a time and recomputing everything in it.

Why two bias vectors replace the query

In the absolute-position form of attention, the query's own position embedding multiplies both the content and the position of each key. Once positions are relative, the query's absolute position carries no information. The paper replaces that part of the query with two learned vectors shared across positions: u, which learns how much any query should favour a key's content, and v, which learns how much any query should favour a given distance.

What it adds to earlier relative positions

Shaw, Uszkoreit and Vaswani introduced relative position representations in 2018, for translation, using learned embeddings for clipped distances and only the first two of the four terms. Transformer-XL encodes distance with fixed sinusoids, so a memory longer than any seen in training still has encodings, and adds the two global bias terms. It also drops Shaw et al.'s relative term on the values.

• SG(·) — stop-gradient: the cached states are used in the forward pass but receive no gradient.
• ∘ — concatenation along the length dimension, memory first.
• hτ^n−1 — the previous segment's states at the layer below; the memory.
• qi, xj — the query's content and the key token's content at this layer.
• Ri−j — a sinusoidal encoding of the distance, with no trained parameters.
• Wk,E, Wk,R — separate key projections for content and for distance.
• u, v — learned global biases: how much any query favours a key's content, and a distance.

Term by term, the four parts are content addressing, a content-dependent distance bias, a global content bias and a global distance bias. At the extremes: with an empty memory the model is an ordinary segment-level transformer and context fragmentation returns. Without the stop-gradient, backpropagation would run through every earlier segment, and memory and compute would grow with the whole history. Remove the two R terms and attention loses explicit distance information inside the window.

The paper evaluates on five standard language-modeling benchmarks: two character-level (enwik8 and text8, scored in bits per character) and three word-level (WikiText-103 and One Billion Word for long and short contexts, and the small Penn Treebank, scored in perplexity). Lower is better throughout.

To measure how far back a model actually uses context, the paper defines relative effective context length (RECL). By that measure Transformer-XL used dependencies about 80% longer than recurrent networks and 450% longer than vanilla Transformers. Evaluation with the cache was more than 1,800 times faster than the vanilla sliding-window procedure at the longest attention length tested.

The ablations separate the two mechanisms. On WikiText-103, the paper's relative encoding beat both Shaw et al.'s relative encoding and absolute encodings when recurrence was used, and absolute encodings could not use a memory longer at test time than in training. The most telling ablation is on One Billion Word, whose sentences are shuffled so that there is no long-range dependency to find. Recurrence still improved perplexity there. The authors attribute that to removing context fragmentation, the arbitrary severing of context at segment starts, not to longer context.

The weakest result is the small one: on Penn Treebank the gain was under one perplexity point, and memory cost grows linearly with how far back the cache reaches.

Two limits are structural and acknowledged. The cache costs memory proportional to how far back you want to see, so "longer context" is bought at a linear price rather than being free. And because no gradient flows into the cached states, the recurrence is not trained as recurrence — the model learns to read a memory it never learns to write, which bounds what the mechanism can become.

Its evaluation is also on language-modelling perplexity over long documents, which measures whether distant context helps prediction on average. That is a genuinely different question from whether the model can retrieve a specific fact from far back, which is the metric the top of this ladder is argued on, and the two do not move together.

How it held up: the recurrence-over-segments idea was largely bypassed, and the two things it invented became universal. Caching computed keys and values so they are not recomputed is now simply how transformer inference works — every serving stack on the serving ladder is organised around managing that cache — and relative position encoding is the direct ancestor of rotary embeddings. A paper whose headline architecture faded while both of its supporting mechanisms became defaults is a common and underrated shape.

Transformer-XL delivered concrete gains that mattered at the time:

It was, for a period, the standard for long-sequence language modeling, and it seeded XLNet (which built its permutation language modeling on the Transformer-XL backbone). Its ideas became reference points for how to think about memory and position in transformers.

Two of Transformer-XL's contributions outlived the specific model. Relative positional encoding became a lasting theme — the recognition that transformers should reason about distance rather than absolute index runs directly into RoPE and the relative-bias schemes used across modern models. And the idea of a recurrent memory — carrying compressed past state forward instead of re-attending to raw tokens — recurs in memory-augmented and state-space models aiming at very long context.

The broader arc is instructive. Long context has been attacked from several directions: sparse attention (Longformer), efficient exact attention (FlashAttention), and recurrence/memory (Transformer-XL). Each trades differently, and the field still borrows from all three. Transformer-XL's specific answer — recur across segments, encode position relatively — was an early, influential statement that a transformer's context needn't end where its window does.

Work each one out before you open it — a number, a prediction or a reason, not a definition. Producing the answer is what makes it stick. Your progress is kept on this device.

Attention costs quadratic in sequence length. Six attempts to escape that, ending with two 2026 papers that give the model a memory instead.

1. 1Transformer-XL2019
2. 2Longformer2020
3. 3Ring Attention2023
4. 4Mamba2023
5. 5Titans2025
6. 6Engram2026

All 110 papers, in 19 ladders →