# 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.

Source: https://www.mlfoundry.in/learn/transformer-xl  
Section: Deep Learning › Attention and Transformer Architectures  
Level: advanced · 14 min read · updated 2026-10-12

**Transformer-XL:** is a decoder-only language model that processes a long text as consecutive segments of $n$ 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 $[\mathrm{SG}(\text{memory});\,\text{current states}]$, where $\mathrm{SG}$ is stop-gradient. Positions are encoded **relatively**: the attention score between $i$ and $j$ depends on the distance $i-j$, through a sinusoid $R_{i-j}$ and two learned global bias vectors $u$ and $v$. 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

$$
\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^{\ell}_{\tau}\in\mathbb R^{n\times d}$: layer-$\ell$ hidden states of segment $\tau$ ($n$ tokens)
- $\circ$: concatenation along the time axis: $M+n$ key/value positions, $n$ query positions
- $\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)**)
- $M$: memory length per layer; the paper sets $M$ equal to the segment length in training and makes it several times longer at evaluation
- $\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 $\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 $N$ layers the longest possible dependency is $O(N\times n)$, against $n$ 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 $U_{1:n}$, token 3 of segment $\tau$ and token 3 of segment $\tau+1$ get identical position encodings even though they are $n$ 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 $(E_{x_i}+U_i)^{\top}W_q^{\top}W_k(E_{x_j}+U_j)$ gives four terms. Transformer-XL rewrites each one:

$$
A^{\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}}
$$

- $R_{i-j}$: a sinusoid encoding of the distance (no parameters), replacing the absolute $U_j$
- $u,\,v\in\mathbb R^{d}$: learned vectors replacing $U_i^{\top}W_q^{\top}$: the query's own position should not matter, so its contribution is the same for every $i$
- $W_{k,E},\;W_{k,R}$: separate key projections for content and for position
- $E_{x}$: in layer $\ell>1$ the content is the hidden state $\tilde h^{\ell-1}$, not the embedding

Terms (b) and (d) need $W_{k,R}R_{i-j}$ for every pair, but only $M+n$ distinct distances exist. The paper computes $W_{k,R}R_k$ once for $k=0\dots M+n-1$, multiplies by the queries to get an $n\times(M+n)$ matrix indexed by distance, and then **shifts** row $i$ left by $n-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 $M$ hidden states, stop-gradient
- **Position:** relative sinusoid $R_{i-j}$ in every layer, learned $u$, $v$, separate $W_{k,R}$
- **Longest dependency:** $O(N\times n)$ for $N$ layers and segment length $n$
- **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

> Figure: 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=2$. For query $i$ and a key three tokens back ($i-j=3$): $W_qE_{x_i}=(1,\,0.5)$, $W_{k,E}E_{x_j}=(0.8,\,-0.2)$, $W_{k,R}R_3=(0.3,\,0.6)$, $u=(0.2,\,0.1)$, $v=(-0.1,\,0.4)$.

**The four terms of A_rel**

1. (a) content: $(1,0.5)\cdot(0.8,-0.2)=0.80-0.10=0.70$.
2. (b) content-dependent position: $(1,0.5)\cdot(0.3,0.6)=0.30+0.30=0.60$.
3. (c) global content bias: $u\cdot(0.8,-0.2)=0.16-0.02=0.14$. It favours keys with this content whatever the query is.
4. (d) global position bias: $v\cdot(0.3,0.6)=-0.03+0.24=0.21$. It favours distance 3 whatever the content is.
5. $A^{\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 $U_i,U_j$ that repeat per segment, a key $n$ tokens further back would get the same position terms as this one.

Dependency length of the query at the last position (i = 47) for different depths, segments and memories (computed with the figure's code)

| layers N | segment n | memory M | vanilla | Transformer-XL | states cached in its cone |
| --- | --- | --- | --- | --- | --- |
| 4 | 8 | 0 | 7 | 7 | 0 |
| 4 | 8 | 1 | 7 | 32 | 27 |
| 4 | 8 | 8 | 7 | 39 | 48 |
| 2 | 8 | 8 | 7 | 23 | 8 |
| 4 | 6 | 6 | 5 | 29 | 36 |
| 6 | 6 | 6 | 5 | 41 | 90 |

With $M=n$ the reach is $N\cdot n$ plus the query's offset in its segment ($4\cdot8+7=39$). Even $M=1$ gives $N\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
import torch, torch.nn as nn, torch.nn.functional as F

def sinusoid(klen, d):
    # R_k for distances k = klen-1, ..., 1, 0 (descending, as in the paper's code)
    pos = torch.arange(klen - 1, -1, -1.0)
    inv = 1 / (10000 ** (torch.arange(0, d, 2.0) / d))
    ang = pos[:, None] * inv[None, :]
    return torch.cat([ang.sin(), ang.cos()], -1)                       # (klen, d)

def rel_shift(x):
    # x (B, H, n, klen) indexed by distance; returns scores indexed by key position
    B, H, n, klen = x.shape
    x = F.pad(x, (1, 0))                                                # (B, H, n, klen+1)
    x = x.view(B, H, klen + 1, n)[:, :, 1:].reshape(B, H, n, klen)
    return x

class RelAttention(nn.Module):
    def __init__(self, d, H):
        super().__init__()
        self.H, self.dh = H, d // H
        self.qkv = nn.Linear(d, 3 * d, bias=False)
        self.r = nn.Linear(d, d, bias=False)                             # W_{k,R}
        self.u = nn.Parameter(torch.zeros(H, self.dh))                  # global content bias
        self.v = nn.Parameter(torch.zeros(H, self.dh))                  # global position bias
        self.o = nn.Linear(d, d, bias=False)
        self.ln = nn.LayerNorm(d)

    def forward(self, h, mem):
        # h (B, n, d) current segment, mem (B, M, d) cached states of the layer below
        B, n, d = h.shape
        cat = torch.cat([mem.detach(), h], 1)                           # SG(memory) ∘ h
        klen = cat.size(1)
        q = self.qkv(h)[..., :d]                                        # queries: current segment only
        k, v = self.qkv(cat)[..., d:].chunk(2, -1)                      # keys/values: memory + segment
        q, k, v = (t.view(B, -1, self.H, self.dh).transpose(1, 2) for t in (q, k, v))
        R = self.r(sinusoid(klen, d).to(h)).view(klen, self.H, self.dh).transpose(0, 1)  # (H, klen, dh)
        ac = (q + self.u[:, None]) @ k.transpose(-1, -2)                # terms (a) + (c)
        bd = rel_shift((q + self.v[:, None]) @ R.transpose(-1, -2))     # terms (b) + (d)
        score = (ac + bd) / self.dh ** 0.5                              # (B, H, n, klen)
        M = klen - n
        causal = torch.ones(n, klen, dtype=torch.bool).triu(M + 1)     # query i sees keys <= M + i
        a = score.masked_fill(causal, float("-inf")).softmax(-1) @ v   # (B, H, n, dh)
        return self.ln(h + self.o(a.transpose(1, 2).reshape(B, n, d)))

d, H, n, M, N = 64, 4, 6, 6, 3
layers = nn.ModuleList(RelAttention(d, H) for _ in range(N))            # (MLPs omitted for brevity)
mems = [torch.zeros(2, 0, d) for _ in range(N)]                        # empty memory per layer input
for segment in torch.randn(4, 2, n, d):                                 # 4 consecutive segments, batch 2
    h, new_mems = segment, []
    for layer, mem in zip(layers, mems):
        new_mems.append(torch.cat([mem, h], 1)[:, -M:].detach())        # cache this layer's input
        h = layer(h, mem)
    mems = new_mems
print(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

> **Memory is cached per layer input, not per layer output:** Layer $\ell$ attends to the cache of layer $\ell-1$ (the embeddings for $\ell=1$). Storing the outputs and feeding them back into the same layer makes a different model and breaks the $O(N\times n)$ argument. Also detach the memory before storing it. Otherwise the autograd graph links every segment back to the start of the document, and memory grows without bound.

> **Why u and v replace the query position:** In the absolute expansion, $U_i^{\top}W_q^{\top}$ multiplies every key. Under recurrence the query's absolute position is meaningless: what matters is what the key is and how far away it is. Replacing $U_i^{\top}W_q^{\top}$ with $u^{\top}$ (for content) and $v^{\top}$ (for distance) keeps these useful biases, and removes the dependence on $i$. In the worked example they contribute 0.14 and 0.21 of the score 1.65.

> **Shared positions across the batch:** $R$ depends only on distances, so it is computed once per forward pass and shared by all sequences in the batch, all queries and all segments. Only the projection $W_{k,R}$ is learned, one per layer. Compare **Rotary positional embeddings (RoPE)** and **ALiBi**, later schemes that also make attention depend on $i-j$ without a separate key projection.

**Strengths**

- Context grows with depth: about $N\times n$ tokens instead of $n$
- 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

**Limitations**

- 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

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

- A. To make the model reversible
- B. So backpropagation and activation memory stay within the current segment, while the forward pass still uses earlier context
- C. Because relative position encodings cannot be differentiated
- D. To prevent the model from attending to future tokens

**Answer:** B. So backpropagation and activation memory stay within the current segment, while the forward pass still uses earlier context — $\mathrm{SG}(h_\tau)$ is a constant during the backward pass. Training cost then depends on $n+M$, not on the length of the document, exactly like truncated BPTT in RNNs. The causal mask, not stop-gradient, prevents attention to the future.

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

- A. Nothing, attention is permutation-invariant
- B. Keys in the memory and in the current segment share the position indices 0…3, so two tokens 4 positions apart look equally far away
- C. The causal mask stops working
- D. The memory has to be recomputed every step

**Answer:** B. Keys in the memory and in the current segment share the position indices 0…3, so two tokens 4 positions apart look equally far away — Token $j$ of segment $\tau$ and token $j$ of segment $\tau+1$ get the same $U_j$ but are 4 positions apart, and both are visible to the query. Relative encoding uses $R_{i-j}$, so distances $0\dots M+n-1$ stay distinct. The figure counts these collisions: 12 of 12 keys share an index when $M=n=6$.

**Key points**

- Recurrence: $\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\times n)$.
- Relative score $A_{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.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
