Transformer-XL

Transformer-XL (Dai et al., 2019) caches each layer's hidden states from the previous segment and lets the next segment attend to them without gradient. Relative positional encodings with learned biases u and v keep positions consistent, so context grows with depth past the segment edge.

14 min read990 wordsadvanced0 viewsupdated 2026-10-12

Definition

Transformer-XL is a decoder-only language model that processes a long text as consecutive segments of nn tokens and adds segment-level recurrence. After a segment is processed, every layer's hidden states are stored as memory. When the next segment runs, each layer attends to [SG(memory); current states][\mathrm{SG}(\text{memory});\,\text{current states}], where SG\mathrm{SG} is stop-gradient. Positions are encoded relatively: the attention score between ii and jj depends on the distance i−ji-j, through a sinusoid Ri−jR_{i-j} and two learned global bias vectors uu and vv. It was introduced by Dai, Yang, Yang, Carbonell, Le and Salakhutdinov in "Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context" (ACL 2019).

A vanilla transformer language model can only be trained on fixed-length chunks. Al-Rfou et al. (2018) trained a 64-layer character model this way: split the corpus into segments, train on each segment independently. That has two costs. No information flows across a segment boundary, so the longest dependency the model can learn is the segment length. And the first tokens of every segment are predicted with almost no context, which the authors call context fragmentation. At evaluation the vanilla model slides its window one token at a time and recomputes the whole segment for every prediction, which is very slow.

Transformer-XL fixes both problems with the recurrence idea from RNNs, applied per layer instead of per token. On release it set new results on all five standard language-modelling benchmarks (abstract): 0.99 bits per character on enwik8, 1.08 on text8, perplexity 18.3 on WikiText-103, 21.8 on One Billion Word and 54.5 on Penn Treebank without fine-tuning. The paper reports dependencies about 80% longer than RNNs and 450% longer than vanilla transformers, and evaluation up to 1,800+ times faster than the vanilla model. XLNet (Yang et al., 2019) was built on it.

Segment-level recurrence

h~τ+1 ℓ−1=[ SG(hτℓ−1)  ∘  hτ+1ℓ−1 ]qτ+1ℓ,  kτ+1ℓ,  vτ+1ℓ=hτ+1ℓ−1Wq⊤,    h~τ+1 ℓ−1Wk⊤,    h~τ+1 ℓ−1Wv⊤hτ+1ℓ=Transformer-Layer(qτ+1ℓ,kτ+1ℓ,vτ+1ℓ)\begin{aligned}\tilde h^{\,\ell-1}_{\tau+1}&=\big[\,\mathrm{SG}(h^{\ell-1}_{\tau})\;\circ\;h^{\ell-1}_{\tau+1}\,\big]\\ q^{\ell}_{\tau+1},\;k^{\ell}_{\tau+1},\;v^{\ell}_{\tau+1}&=h^{\ell-1}_{\tau+1}W_q^{\top},\;\;\tilde h^{\,\ell-1}_{\tau+1}W_k^{\top},\;\;\tilde h^{\,\ell-1}_{\tau+1}W_v^{\top}\\ h^{\ell}_{\tau+1}&=\text{Transformer-Layer}\big(q^{\ell}_{\tau+1},k^{\ell}_{\tau+1},v^{\ell}_{\tau+1}\big)\end{aligned}
hτℓ∈Rn×dh^{\ell}_{\tau}\in\mathbb R^{n\times d}
layer-ℓ\ell hidden states of segment τ\tau (nn tokens)
∘\circ
concatenation along the time axis: M+nM+n key/value positions, nn query positions
SG\mathrm{SG}
stop-gradient: the memory is a constant, so backpropagation stays inside the current segment, like truncated BPTT (see Truncated backpropagation through time (TBPTT))
MM
memory length per layer; the paper sets MM equal to the segment length in training and makes it several times longer at evaluation
Transformer-Layer\text{Transformer-Layer}
causal attention over memory + current prefix, then the position-wise MLP, with residuals and LayerNorm

Queries come only from the current segment. Keys and values come from the memory and the current segment, with the usual causal mask inside the segment. The cache is per layer: layer ℓ\ell reads the memory of layer ℓ−1\ell-1, not its own. So the dependency grows by about one segment per layer: a state in the memory already summarises the segment before it. With NN layers the longest possible dependency is O(N×n)O(N\times n), against nn for the vanilla model. Compare an RNN, whose hidden state is shifted in time within one layer; Transformer-XL shifts it one layer down.

Relative positional encoding

Recurrence breaks absolute positions. If each segment adds the same embeddings U1:nU_{1:n}, token 3 of segment τ\tau and token 3 of segment τ+1\tau+1 get identical position encodings even though they are nn apart, and both sit in the same attention window. The fix is to inject only relative distance, inside the score, in every layer (building on Shaw et al., 2018). Expanding the absolute score (Exi+Ui)⊤Wq⊤Wk(Exj+Uj)(E_{x_i}+U_i)^{\top}W_q^{\top}W_k(E_{x_j}+U_j) gives four terms. Transformer-XL rewrites each one:

Ai,jrel=Exi⊤Wq⊤Wk,E Exj⏟(a) content+Exi⊤Wq⊤Wk,R Ri−j⏟(b) content-dependent position+u⊤Wk,E Exj⏟(c) global content bias+v⊤Wk,R Ri−j⏟(d) global position biasA^{\text{rel}}_{i,j}=\underbrace{E_{x_i}^{\top}W_q^{\top}W_{k,E}\,E_{x_j}}_{(a)\ \text{content}}+\underbrace{E_{x_i}^{\top}W_q^{\top}W_{k,R}\,R_{i-j}}_{(b)\ \text{content-dependent position}}+\underbrace{u^{\top}W_{k,E}\,E_{x_j}}_{(c)\ \text{global content bias}}+\underbrace{v^{\top}W_{k,R}\,R_{i-j}}_{(d)\ \text{global position bias}}
Ri−jR_{i-j}
a sinusoid encoding of the distance (no parameters), replacing the absolute UjU_j
u, v∈Rdu,\,v\in\mathbb R^{d}
learned vectors replacing Ui⊤Wq⊤U_i^{\top}W_q^{\top}: the query's own position should not matter, so its contribution is the same for every ii
Wk,E,  Wk,RW_{k,E},\;W_{k,R}
separate key projections for content and for position
ExE_{x}
in layer ℓ>1\ell>1 the content is the hidden state h~ℓ−1\tilde h^{\ell-1}, not the embedding

Terms (b) and (d) need Wk,RRi−jW_{k,R}R_{i-j} for every pair, but only M+nM+n distinct distances exist. The paper computes Wk,RRkW_{k,R}R_k once for k=0…M+n−1k=0\dots M+n-1, multiplies by the queries to get an n×(M+n)n\times(M+n) matrix indexed by distance, and then shifts row ii left by n−1−in-1-i to turn it into the matrix indexed by key position. This keeps the positional part linear in the number of distances instead of quadratic. The result is a model whose attention depends on how far back a token is, not on where a segment started, so the memory can be made longer at evaluation than in training.

Transformer-XL at a glance

Authors / venue
Dai, Yang, Yang, Carbonell, Le, Salakhutdinov (Carnegie Mellon University and Google Brain), ACL 2019
Recurrence
per-layer cache of the previous MM hidden states, stop-gradient
Position
relative sinusoid Ri−jR_{i-j} in every layer, learned uu, vv, separate Wk,RW_{k,R}
Longest dependency
O(N×n)O(N\times n) for NN layers and segment length nn
Results (abstract)
enwik8 0.99 bpc, text8 1.08 bpc, WikiText-103 18.3 ppl, One Billion Word 21.8 ppl, Penn Treebank 54.5 ppl
Evaluation speed
up to 1,800+ times faster than a vanilla transformer that recomputes its window per token
Descendants
XLNet (2019), the Compressive Transformer (2019), relative-position schemes in later models
h̃ = [SG(memory of M states) ∘ h of current segment]; q from segment, k, v from h̃□ query · ■ in current segment (gets gradient) · ■ cached, stop-gradients0s1s2s3s4s5s6s7embℓ=1ℓ=2ℓ=3ℓ=4absi−j0·1·2·3·4·5·0·1·2·3·4·5·0·1·2·3·4·5·0·1·2·3·4·5·0·1·2·3·4·5·0·1·2·3·4·5·01111029384756051423324150keys of the query (coloured): per-segment absolute index repeats; relative distance does notdependency length 29 tokensvanilla bound n − 1 = 5paper's O(N·n) N·n = 24states in cone 55 (36 cached)keys per query 12 = M 6 + 6 in segmentambiguous abs. index 12 of 12eval states/new token 4 (vanilla 24)cache size N·M = 24 vectorsClick a top-row cell to move the query. Vanilla: each segment starts from scratch, so the querysees only its own segment. XL: every layer also reads the cache, and a cached state saw its ownsegment, so the reach grows by about a segment per layer; gradients stay in the current segment.N = 4 layers · n = 6 · M = 6 · query at i = 47, segment starts at s = 42
model
fig.Rows are layers (emb at the bottom), columns are 48 token positions cut into segments of n. The top-right cell is the query; blue states are in its segment and get gradients, violet ones are cached memory under stop-gradient. Defaults N = 4, n = 6, M = 6: the query at i = 47 depends on tokens back to position 18, a dependency of 29 = N·n + 5. Its cone has 55 hidden states, 36 of them cached. Switch to vanilla and the dependency falls to 5 = n − 1. Set M = 1 with N = 6: the reach is still 36 tokens, because the single cached state is the last one of the previous segment, which saw that whole segment one layer down. With M = n each query sees 12 keys. Under per-segment absolute positions all 12 have an index that occurs twice, while the relative distances 0…11 are unique. At evaluation a vanilla model recomputes n·N = 24 states per new token; Transformer-XL computes N = 4.

Worked example: one relative score, and how far the context reaches

Take a head with d=2d=2. For query ii and a key three tokens back (i−j=3i-j=3): WqExi=(1, 0.5)W_qE_{x_i}=(1,\,0.5), Wk,EExj=(0.8, −0.2)W_{k,E}E_{x_j}=(0.8,\,-0.2), Wk,RR3=(0.3, 0.6)W_{k,R}R_3=(0.3,\,0.6), u=(0.2, 0.1)u=(0.2,\,0.1), v=(−0.1, 0.4)v=(-0.1,\,0.4).

The four terms of A_rel

  1. 1(a) content: (1,0.5)⋅(0.8,−0.2)=0.80−0.10=0.70(1,0.5)\cdot(0.8,-0.2)=0.80-0.10=0.70.
  2. 2(b) content-dependent position: (1,0.5)⋅(0.3,0.6)=0.30+0.30=0.60(1,0.5)\cdot(0.3,0.6)=0.30+0.30=0.60.
  3. 3(c) global content bias: u⋅(0.8,−0.2)=0.16−0.02=0.14u\cdot(0.8,-0.2)=0.16-0.02=0.14. It favours keys with this content whatever the query is.
  4. 4(d) global position bias: v⋅(0.3,0.6)=−0.03+0.24=0.21v\cdot(0.3,0.6)=-0.03+0.24=0.21. It favours distance 3 whatever the content is.
  5. 5Ai,jrel=0.70+0.60+0.14+0.21=1.65A^{\text{rel}}_{i,j}=0.70+0.60+0.14+0.21=1.65. Move the same pair to the next segment: the distance is still 3, so the score is still 1.65. With absolute Ui,UjU_i,U_j that repeat per segment, a key nn tokens further back would get the same position terms as this one.
layers Nsegment nmemory MvanillaTransformer-XLstates cached in its cone
480770
48173227
48873948
2887238
46652936
66654190
Dependency length of the query at the last position (i = 47) for different depths, segments and memories (computed with the figure's code)

With M=nM=n the reach is N⋅nN\cdot n plus the query's offset in its segment (4⋅8+7=394\cdot8+7=39). Even M=1M=1 gives N⋅n=32N\cdot n=32, because information hops through the last state of each earlier segment. A longer memory does not increase the hop count much, but it lets each layer read those tokens directly rather than through a compressed summary. That is why the paper uses longer memories at evaluation time.

python
1import torch, torch.nn as nn, torch.nn.functional as F
2
3def sinusoid(klen, d):
4 # R_k for distances k = klen-1, ..., 1, 0 (descending, as in the paper's code)
5 pos = torch.arange(klen - 1, -1, -1.0)
6 inv = 1 / (10000 ** (torch.arange(0, d, 2.0) / d))
7 ang = pos[:, None] * inv[None, :]
8 return torch.cat([ang.sin(), ang.cos()], -1) # (klen, d)
9
10def rel_shift(x):
11 # x (B, H, n, klen) indexed by distance; returns scores indexed by key position
12 B, H, n, klen = x.shape
13 x = F.pad(x, (1, 0)) # (B, H, n, klen+1)
14 x = x.view(B, H, klen + 1, n)[:, :, 1:].reshape(B, H, n, klen)
15 return x
16
17class RelAttention(nn.Module):
18 def __init__(self, d, H):
19 super().__init__()
20 self.H, self.dh = H, d // H
21 self.qkv = nn.Linear(d, 3 * d, bias=False)
22 self.r = nn.Linear(d, d, bias=False) # W_{k,R}
23 self.u = nn.Parameter(torch.zeros(H, self.dh)) # global content bias
24 self.v = nn.Parameter(torch.zeros(H, self.dh)) # global position bias
25 self.o = nn.Linear(d, d, bias=False)
26 self.ln = nn.LayerNorm(d)
27
28 def forward(self, h, mem):
29 # h (B, n, d) current segment, mem (B, M, d) cached states of the layer below
30 B, n, d = h.shape
31 cat = torch.cat([mem.detach(), h], 1) # SG(memory) ∘ h
32 klen = cat.size(1)
33 q = self.qkv(h)[..., :d] # queries: current segment only
34 k, v = self.qkv(cat)[..., d:].chunk(2, -1) # keys/values: memory + segment
35 q, k, v = (t.view(B, -1, self.H, self.dh).transpose(1, 2) for t in (q, k, v))
36 R = self.r(sinusoid(klen, d).to(h)).view(klen, self.H, self.dh).transpose(0, 1) # (H, klen, dh)
37 ac = (q + self.u[:, None]) @ k.transpose(-1, -2) # terms (a) + (c)
38 bd = rel_shift((q + self.v[:, None]) @ R.transpose(-1, -2)) # terms (b) + (d)
39 score = (ac + bd) / self.dh ** 0.5 # (B, H, n, klen)
40 M = klen - n
41 causal = torch.ones(n, klen, dtype=torch.bool).triu(M + 1) # query i sees keys <= M + i
42 a = score.masked_fill(causal, float("-inf")).softmax(-1) @ v # (B, H, n, dh)
43 return self.ln(h + self.o(a.transpose(1, 2).reshape(B, n, d)))
44
45d, H, n, M, N = 64, 4, 6, 6, 3
46layers = nn.ModuleList(RelAttention(d, H) for _ in range(N)) # (MLPs omitted for brevity)
47mems = [torch.zeros(2, 0, d) for _ in range(N)] # empty memory per layer input
48for segment in torch.randn(4, 2, n, d): # 4 consecutive segments, batch 2
49 h, new_mems = segment, []
50 for layer, mem in zip(layers, mems):
51 new_mems.append(torch.cat([mem, h], 1)[:, -M:].detach()) # cache this layer's input
52 h = layer(h, mem)
53 mems = new_mems
54print(h.shape, mems[0].shape) # torch.Size([2, 6, 64]) torch.Size([2, 6, 64])
Relative multi-head attention with memory (Transformer-XL), including the shift trick and the memory update

Use when

  • +Context grows with depth: about N×nN\times n tokens instead of nn
  • +No context fragmentation: the first tokens of a segment still see the previous one
  • +Fast evaluation: each new token reuses the cache instead of recomputing a window
  • +Relative positions generalise to memories longer than in training

Avoid when

  • −Gradients never cross a segment boundary, so long-range credit assignment is truncated
  • −The cache costs N·M·d floats per sequence and must be carried between batches in order
  • −Training data must be fed as contiguous streams, not shuffled independent chunks
  • −The relative-attention kernel with the shift trick is more complex than standard attention

Check yourself

Why does Transformer-XL apply stop-gradient to the cached memory?

Check yourself

A Transformer-XL model with segment length n = 4 used per-segment absolute position embeddings instead of relative ones. What goes wrong?

Remember

  • ✓Recurrence: h~τ+1ℓ−1=[SG(hτℓ−1)∘hτ+1ℓ−1]\tilde h^{\ell-1}_{\tau+1}=[\mathrm{SG}(h^{\ell-1}_\tau)\circ h^{\ell-1}_{\tau+1}]; queries from the segment, keys and values from memory + segment; reach O(N×n)O(N\times n).
  • ✓Relative score Aij=qi⊤kj+qi⊤Wk,RRi−j+u⊤kj+v⊤Wk,RRi−jA_{ij}=q_i^\top k_j+q_i^\top W_{k,R}R_{i-j}+u^\top k_j+v^\top W_{k,R}R_{i-j}: content, content-position, global content bias, global position bias.
  • ✓Stop-gradient keeps training cost per segment constant, like truncated BPTT; the cache is per layer input.
  • ✓Dai et al., ACL 2019: enwik8 0.99 bpc, WikiText-103 18.3 ppl, up to 1,800+× faster evaluation than a vanilla sliding window.
  • ✓The shift trick computes the positional terms from M + n distance vectors instead of one per pair.
← back to Deep Learning roadmap