Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context

ArXiv: 1901.02860

🎯 Pitch

Vanilla Transformers forget everything beyond a fixed-length segment, shattering long-range context. Transformer-XL reuses hidden states from previous segments as memory, simultaneously enabling dependencies 450% longer than standard Transformers and slashing evaluation time by a factor of 1,800×.

1. Executive Summary

This paper introduces Transformer-XL, a novel neural architecture that enables Transformer-based language models to learn dependencies beyond a fixed-length context without disrupting temporal coherence. Using a segment-level recurrence mechanism (caching and reusing hidden states from previous segments as extended memory) and a novel relative positional encoding scheme (encoding pairwise distance between tokens rather than absolute positions), Transformer-XL achieves substantially longer effective context on benchmarks including WikiText-103 and enwik8 with PaLM 2-style Transformer models. The architecture learns dependency that is 80% longer than RNNs and 450% longer than vanilla Transformers, reduces perplexity on WikiText-103 from 20.5 to 18.3 (state-of-the-art), and delivers up to 1,800× faster evaluation than vanilla Transformers by reusing cached representations, establishing that recurrence and relative position encoding together resolve both the context fragmentation problem and the temporal confusion that would otherwise make state reuse impossible.

2. Context and Motivation

The Core Problem: Transformers Have a Fixed-Length Context Ceiling

The fundamental tension that Transformer-XL addresses is deceptively simple: Transformer architectures are theoretically capable of modeling arbitrarily long dependencies, but in practice they are constrained to a fixed-length context window during language model training. This is not a theoretical limitation of the attention mechanism itself — the direct connections between all token pairs in a sequence should, in principle, allow a Transformer to capture relationships across thousands of tokens without the gradient vanishing problems that plague RNNs. Instead, it is a practical training constraint that arises from how Transformers are applied to the language modeling task.

To understand why this matters, consider the standard language modeling objective. Given a corpus of tokens $\mathbf{x} = (x_1, \dots, x_T)$ , the goal is to estimate the joint probability $P(\mathbf{x})$ , which is auto-regressively factorized as:

$P(\mathbf{x}) = \prod_t P(x_t \mid \mathbf{x}_{<t})$

A trainable neural network encodes the preceding context $\mathbf{x}_{<t}$ into a fixed-size hidden state, which is then used to predict the next token. In an ideal world with infinite memory and computation, you would simply feed the entire history of tokens into an unconditional Transformer decoder and train on the full sequence. This is computationally infeasible for corpora containing millions or billions of tokens — the self-attention mechanism has quadratic complexity in the sequence length, meaning that processing a 100,000-token sequence costs 10,000× more than processing a 1,000-token one.

The standard workaround, adopted by Al-Rfou et al. (2018) in their character-level Transformer language model, is to split the corpus into fixed-length segments of a manageable size (a few hundred tokens) and train the model only within each segment, with no information flow across segment boundaries. This is what the authors call the vanilla Transformer LM. Figure 1a in the paper illustrates this: the corpus is chopped into consecutive chunks, and the model processes each chunk independently with zero context from previous chunks.

This training paradigm creates two critical pathologies, both of which the paper identifies and names:

Pathology 1: The Hard Upper Bound on Dependency Length

Because information never flows across segments during training, the maximum dependency that the model can learn is capped at the segment length. If segments are 128 tokens long, the model cannot learn that a pronoun in position 500 refers to a name mentioned in position 100 — those positions fall into different segments and are never seen together during training. This is particularly damaging because the self-attention mechanism's primary advantage over RNNs is precisely its ability to directly connect distant positions. The vanilla training procedure discards this advantage by preventing those connections from ever being formed.

The authors cite empirical evidence that this matters: Khandelwal et al. (2018) found that LSTM language models use only about 200 context words on average, suggesting that even RNNs — which can in principle propagate information across arbitrary distances — are not fully exploiting available context. A fixed-length Transformer trained on 128-token segments would be even more severely constrained, unable to learn dependencies beyond those 128 positions regardless of how capable the attention mechanism is.

Pathology 2: Context Fragmentation

The fixed-length segments are created by selecting consecutive chunks of symbols without respecting sentence boundaries, paragraph breaks, or any other semantic structure. This means that the first few tokens in each segment lack necessary preceding context. Consider a segment that starts mid-sentence: the model has no access to the subject of the sentence, the topic of the paragraph, or any other contextual cues that would make the first few predictions well-informed.

This is not merely a question of those initial tokens having higher perplexity — it creates a systematic problem for optimization. The model is forced to learn two conflicting behaviors: predict tokens with full context (most positions in the segment) and predict tokens with zero context (the first few positions). The paper argues this leads to "inefficient optimization and inferior performance" because the model's parameters receive contradictory gradients from these two regimes.

The authors note that using padding to align segments with sentence boundaries is theoretically possible, but "in practice it has been standard practice to simply chunk long text into fixed-length segments due to improved efficiency" — a pragmatic concession that directly harms model quality.

Pathology 3: Cripplingly Slow Evaluation

During evaluation, the vanilla model faces a different but related problem. To give each prediction access to the longest possible context (matching what was seen during training), the model must process an entire segment of length $L$ , make only a single prediction at the last position, then shift the segment right by one position and re-process the entire new segment from scratch. Figure 1b illustrates this: for each new token prediction, an entire $L$ -length segment is fed through the network, even though $L-1$ of those tokens were already processed in the previous step.

This means that evaluating a sequence of $T$ tokens with a segment length of $L$ costs $O(T \times L)$ in computation rather than the $O(T)$ that would be possible with incremental processing. For a typical setting with $L = 384$ , each prediction is roughly 384× more expensive than it needs to be. The paper later quantifies this: Transformer-XL achieves up to 1,800× speedup during evaluation compared to this vanilla procedure (Table 9), meaning the vanilla model is wasting 99.94% of its computation on redundant processing.

Why This Problem Matters

The fixed-length context limitation is not an academic curiosity — it has direct consequences for language modeling as a field and for downstream applications built on language models.

Language modeling is a foundational task for unsupervised pretraining. At the time of this paper's writing (2019), a dominant paradigm was emerging: pretrain a language model on large unlabeled corpora, then fine-tune or use the learned representations for downstream tasks. Models like ELMo (Peters et al., 2018), GPT (Radford et al., 2018), and BERT (Devlin et al., 2018) all relied on language modeling or variants thereof as the pretraining objective. If the pretrained model cannot capture dependencies longer than its segment length, the representations it produces will be impoverished for tasks requiring long-range reasoning — document classification, coreference resolution, summarization, question answering over long passages.

The gap between capability and practice is large and growing. Transformers had already demonstrated the ability to outperform LSTMs on language modeling (Al-Rfou et al., 2018) when trained with fixed-length segments, suggesting that even with crippled context, the architecture's other advantages (direct token-to-token connections, parallelizability) outweighed LSTMs' ability to maintain state across longer spans. This implied that fixing the context limitation could unlock substantially larger gains — the model was winning despite fighting with one hand tied behind its back.

Efficiency at inference time is pragmatically critical. Language models deployed in production (for text generation, autocomplete, translation) need to generate tokens one at a time with low latency. The vanilla Transformer's requirement to reprocess the entire context window for every new token makes it prohibitively expensive for real-time applications, regardless of its accuracy. Any solution that enables caching and reuse of previous computations directly translates to lower serving costs and faster response times.

Prior Approaches and Where They Fall Short

The paper situates its contribution within two lineages of prior work: approaches that attempted to extend context in language models generally, and the specific Transformer-based language modeling approach that the paper directly builds on.

RNN-Based Language Models and Their Extensions

LSTMs were the dominant architecture for language modeling prior to Transformers, obtaining strong results on multiple benchmarks (as evidenced by the baseline tables in Section 4.1). However, they suffer from known optimization difficulties:

Gradient vanishing and explosion (Hochreiter et al., 2001): information from early tokens must propagate through many recurrent steps to influence later predictions, and the gradients correspondingly decay or explode. Gating mechanisms in LSTMs and gradient clipping (Graves, 2013) mitigate but do not eliminate this problem.
Empirically limited context usage: Khandelwal et al. (2018) showed that LSTM language models effectively use only about 200 tokens of context on average — far less than the theoretical maximum of their hidden state. This suggests that even when architectures can theoretically maintain long-term memory, optimization difficulties prevent them from doing so in practice.

Various extensions attempted to address these limitations: better initialization (Le et al., 2015), auxiliary loss signals (Trinh et al., 2018), augmented memory structures (Ke et al., 2018; Graves et al., 2014), and modified internal RNN architectures (Wu et al., 2016; Li et al., 2018). These approaches made incremental improvements but did not fundamentally change the optimization landscape — the recurrent pathway remained a bottleneck.

A parallel line of work fed wider context representations directly into the network as additional input, ranging from manually defined context features (Mikolov and Zweig, 2012; Ji et al., 2015) to learned document-level topic models (Dieng et al., 2016; Wang et al., 2017). These approaches extend the information available to the model but do not change how that information is processed — the model still makes predictions from a fixed-size representation, and the quality of that representation depends on how effectively the network can compress arbitrarily long context into a fixed vector.

The Vanilla Transformer LM (Al-Rfou et al., 2018)

Al-Rfou et al. (2018) applied deep Transformer networks to character-level language modeling with auxiliary losses and achieved results that "outperform LSTMs by a large margin" — demonstrating that Transformers could beat RNNs at language modeling despite the fixed-length context limitation. This was an important result because it showed the Transformer's architectural advantages (direct token-to-token attention, no sequential bottleneck for gradient flow) were powerful enough to overcome the handicap of truncated context.

However, the paper identifies specific shortcomings in this approach that Transformer-XL is designed to address:

Training on separated fixed-length segments with no information flow across segments — this is the core limitation. Al-Rfou et al. used segments of "a few hundred characters," meaning the model could not capture dependencies longer than that window regardless of how deep or wide the network was.
Context fragmentation as a consequence of fixed-length chunking — Al-Rfou et al. did not address this problem; their segments were created by selecting consecutive chunks of symbols without regard to semantic boundaries.
The evaluation procedure was extremely expensive — Al-Rfou et al. used the same sliding-window evaluation described above, where each prediction requires processing a full segment from scratch.

The authors position Transformer-XL as directly building on the Al-Rfou et al. Transformer LM while systematically addressing all three of these limitations. The key insight is that these are not inherent properties of the Transformer architecture — they are artifacts of the training procedure (fixed segments) and the positional encoding scheme (absolute positions that prevent state reuse).

Relative Positional Encodings in Prior Work

The idea of using relative rather than absolute positional encodings had been explored before Transformer-XL, notably by Shaw et al. (2018) for machine translation and Huang et al. (2018) for music generation. However, the paper argues that these prior formulations are insufficient for the language modeling setting:

Shaw et al. (2018) parameterized relative position as a learned embedding matrix $\hat{\mathbf{R}}$ that directly produces a bias term added to the attention scores. The paper identifies two limitations:

Their formulation only includes terms equivalent to the content-based addressing (term a) and content-dependent positional bias (term b) in the authors' decomposition, dropping the global content bias and global positional bias terms (terms c and d) that the authors find empirically important.
By merging the multiplication $\mathbf{W}_{k}\mathbf{R}$ into a single trainable matrix $\hat{\mathbf{R}}$ , Shaw et al. abandon the inductive bias built into the original sinusoid positional encoding (Vaswani et al., 2017). The sinusoid encoding has the property that the encoding at position $i + k$ can be represented as a linear function of the encoding at position $i$ , which provides a structural prior that relative distances should behave systematically. Without this inductive bias, the model must learn distance relationships from scratch and cannot generalize to attention lengths longer than those seen during training — a critical limitation for the recurrence mechanism, where evaluation-time memory may be many times longer than training segments.

How This Paper Positions Itself

Transformer-XL is presented not as a rejection of prior approaches but as a synthesis that resolves the tension between the Transformer's theoretical capability and its practical limitations in language modeling. The paper frames the problem as having two interdependent components that must be solved together:

The recurrence mechanism (Section 3.2) solves the fixed-length context problem by caching and reusing hidden states from previous segments, creating a segment-level recurrence that can propagate information across arbitrarily long distances. This directly addresses the dependency length ceiling, context fragmentation, and evaluation inefficiency.
The relative positional encoding scheme (Section 3.3) makes the recurrence mechanism possible by ensuring that reused hidden states do not create temporal confusion. Without relative encodings, the model cannot distinguish whether a token in memory came from the current segment or a previous one, because both would carry the same absolute positional encoding. Relative encodings encode pairwise distances rather than absolute positions, making the model's attention decisions invariant to where a segment falls in the overall sequence.

The paper emphasizes that neither technique alone is sufficient — absolute positional encodings prevent state reuse, and recurrence without proper positional handling causes temporal confusion. The two techniques together "form a complete set of solutions."

Importantly, the paper does not claim to be the first to propose recurrence in neural networks (clearly not — RNNs are the definition of recurrence) or the first to propose relative positional encodings. Instead, it claims to be the first to introduce recurrence into a purely self-attentive model in a way that enables learning dependencies beyond the training segment length, and the first to derive a relative positional encoding formulation that enables this recurrence while maintaining the inductive biases of sinusoid encodings and generalizing to unseen attention lengths.

The positioning relative to RNNs is particularly noteworthy. Rather than framing Transformer-XL as a competitor to RNNs, the paper positions it as achieving what RNNs were designed for (long-range dependency) using a fundamentally different mechanism (self-attention with state reuse) that avoids the optimization difficulties of recurrent architectures. The "XL" in the name — "extra long" — directly signals this ambition: to push the effective context length far beyond what either Transformers or RNNs had previously achieved.

3. Technical Approach

This is primarily an architecture design paper whose core idea is that Transformers can model arbitrarily long dependencies if you give them a mechanism to carry forward hidden states from previous segments (recurrence) and a positional encoding scheme that distinguishes token positions across segment boundaries (relative position encoding) — and that both components are necessary since neither works without the other.

3.1 Reader Orientation

What the system is: Transformer-XL is a modified Transformer decoder architecture that, when trained as a language model on sequential text, can attend to tokens far beyond the current training segment by caching and reusing hidden states from all previously processed segments as an extended memory.

What problem it solves and the shape of the solution: Standard Transformers are constrained to a fixed-length context window during language model training because they process each segment independently with no information flow across boundaries. Transformer-XL introduces a segment-level recurrence mechanism — each new segment's hidden states are computed using the current segment's embeddings plus the previous segment's cached hidden states — and a relative positional encoding scheme that encodes pairwise distances between tokens rather than absolute positions, which is necessary to prevent the model from confusing tokens in different segments that share the same absolute positional encoding when states are reused.

3.2 Big-Picture Architecture (Diagram in Words)

The Transformer-XL architecture has two interdependent components that together solve the fixed-length context problem:

Segment-Level Recurrence with State Reuse: During training, the hidden state sequence computed for the previous segment is frozen (gradients are stopped) and cached to be concatenated with the current segment's hidden states as the extended context for computing keys and values in the self-attention layers. This creates a segment-level recurrent connection — information from segment $\tau-1$ flows into segment $\tau$ at each layer, building an effective context that spans many segments. During evaluation, representations from all previous segments can be reused directly instead of recomputed from scratch, yielding massive speedups.
Relative Positional Encoding: The self-attention mechanism is reformulated to use relative positional encodings rather than absolute ones. Instead of adding an absolute position embedding to each token's input representation, the attention score between any two tokens incorporates their relative distance as a learnable bias injected into the attention computation. This is essential because absolute positional encodings would cause confusion when hidden states from previous segments are reused — the model would see two tokens in the same absolute position within their respective segments and be unable to distinguish them. Relative encodings use pairwise distances, making the attention computation invariant to which segment a token belongs to.

Information flows forward through a Transformer-XL of depth $N$ as follows: A new segment's word embeddings enter layer 1 → the cached hidden states from the previous segment (at the same layer) are stopped-gradient and concatenated to the current segment's hidden states → this extended sequence is used to compute keys and values, while queries come only from the current segment → attention scores incorporate relative position biases (distance between query and key positions) → the output of the attention layer is fed through standard position-wise feed-forward and layer norm operations → this produces the current segment's hidden states for layer 1, which are cached for the next segment → the process repeats for all $N$ layers, with each layer accessing the previous segment's hidden states at that same layer.

3.3 Roadmap for the Deep Dive

First, the formal definition of the vanilla Transformer LM training procedure, including the segment chunking, positional encoding via absolute sinusoids, attention score decomposition, and the evaluation sliding-window inefficiency. This establishes the baseline that Transformer-XL improves upon and makes the recurrence mechanism's motivation concrete.
Second, the segment-level recurrence mechanism — how hidden states from previous segments are cached, stopped-gradient, and concatenated to form the extended context for keys and values. This section covers the training-phase procedure, the evaluation-phase speedup, the analogy to truncated BPTT, and the growing dependency length across layers.
Third, the relative positional encoding reformulation — a complete walkthrough of the four-term decomposition of the standard absolute attention score (terms a, b, c, d), the corresponding reparameterization into the four relative terms (content-based addressing, content-dependent positional bias, global content bias, global positional bias), the introduction of trainable parameters $\mathbf{u}$ and $\mathbf{v}$ , the separation of key weight matrices $\mathbf{W}_{k,E}$ and $\mathbf{W}_{k,R}$ , and the use of the fixed sinusoid encoding matrix $\mathbf{R}$ to provide the inductive bias that enables length generalization.
Fourth, the complete forward-pass equations for a single-layer Transformer-XL that tie everything together — the memory concatenation, the attention score computation with relative biases, the masking, the feed-forward sublayer, and the caching of hidden states for the next segment. This serves as the complete algorithmic specification.
Fifth, a note on the efficient computation of the relative positional bias, since the naive quadratic computation can be reduced to linear cost through a simple matrix-vector multiplication and left-shifting trick.

3.4 Detailed, Sentence-Based Technical Breakdown

Vanilla Transformer Language Model and Its Limitations

The vanilla Transformer language model, as defined by Al-Rfou et al. (2018), processes text by splitting the entire training corpus into fixed-length segments of some pre-chosen length $L$ . Let the $\tau$ -th segment be denoted $\mathbf{s}_\tau = [x_{\tau,1}, \dots, x_{\tau,L}]$ , where each $x_{\tau,i}$ is a token. The model is an unconditional Transformer decoder (a stack of $N$ self-attention layers with causal masking followed by position-wise feed-forward networks and layer normalization) that, for each token position $i$ in segment $\tau$ , computes a hidden state $\mathbf{h}_{\tau,i}^n$ at layer $n$ by attending over all previous positions within the same segment ( $\leq i$ ). The loss is the standard cross-entropy over the vocabulary, computed for every position or for a subset (e.g., only the most recent half of positions, as studied in the ablation experiments).

The critical constraint is that information never flows across segment boundaries in either the forward or backward pass. Segment $\tau+1$ is processed entirely independently of segment $\tau$ — the model has no mechanism to carry forward any representation of what it has already read. This creates the two pathologies described earlier: the maximum dependency length is capped at $L$ , and the first few tokens of each segment lack preceding context (context fragmentation).

Positional encoding in the vanilla model. Since self-attention is permutation-invariant (it has no inherent notion of token order), the standard Transformer injects positional information by adding a sinusoidal positional encoding to the word embeddings at the input layer. Let $\mathbf{U} \in \mathbb{R}^{L_{\max} \times d}$ be the positional encoding matrix, where row $\mathbf{U}_i$ encodes absolute position $i$ within a segment, $d$ is the hidden dimension, and $L_{\max}$ is the maximum segment length. The encoding uses sine and cosine functions of different frequencies:

$U_{i, 2j} = \sin(i / 10000^{2j/d}), \quad U_{i, 2j+1} = \cos(i / 10000^{2j/d})$

The input to the first Transformer layer for segment $\tau$ is then $\mathbf{E}_{\mathbf{s}_\tau} + \mathbf{U}_{1:L}$ , where $\mathbf{E}_{\mathbf{s}_\tau} \in \mathbb{R}^{L \times d}$ is the sequence of word embeddings for the tokens in segment $\tau$ .

Attention score decomposition with absolute positional encodings. In the standard Transformer, the attention score between a query vector at position $i$ and a key vector at position $j$ (within the same segment) is computed as:

$\mathbf{A}^{\text{abs}}_{i,j} = \underbrace{\mathbf{E}_{x_i}^{\top} \mathbf{W}_q^{\top} \mathbf{W}_k \mathbf{E}_{x_j}}_{(a)} + \underbrace{\mathbf{E}_{x_i}^{\top} \mathbf{W}_q^{\top} \mathbf{W}_k \mathbf{U}_j}_{(b)} + \underbrace{\mathbf{U}_i^{\top} \mathbf{W}_q^{\top} \mathbf{W}_k \mathbf{E}_{x_j}}_{(c)} + \underbrace{\mathbf{U}_i^{\top} \mathbf{W}_q^{\top} \mathbf{W}_k \mathbf{U}_j}_{(d)}$

where:

$\mathbf{E}_{x_i} \in \mathbb{R}^d$ is the word embedding of the query token at position $i$ ,
$\mathbf{W}_q, \mathbf{W}_k \in \mathbb{R}^{d \times d}$ are the query and key projection matrices,
$\mathbf{U}_i, \mathbf{U}_j$ are the absolute positional encodings at positions $i$ and $j$ .

What each term computes:

(a) $\mathbf{E}_{x_i}^{\top} \mathbf{W}_q^{\top} \mathbf{W}_k \mathbf{E}_{x_j}$ : the content-to-content interaction — how much the token at position $i$ should attend to the token at position $j$ based purely on their identities (semantics), independent of position.
(b) $\mathbf{E}_{x_i}^{\top} \mathbf{W}_q^{\top} \mathbf{W}_k \mathbf{U}_j$ : the content-to-position interaction — how much the query token's content modulates its attention based on where the key token sits in the sequence.
(c) $\mathbf{U}_i^{\top} \mathbf{W}_q^{\top} \mathbf{W}_k \mathbf{E}_{x_j}$ : the position-to-content interaction — how the query token's own position biases which tokens it attends to, modulated by the key token's content.
(d) $\mathbf{U}_i^{\top} \mathbf{W}_q^{\top} \mathbf{W}_k \mathbf{U}_j$ : the position-to-position interaction — a pure positional prior that depends only on the absolute positions of the two tokens.

Evaluation inefficiency of the vanilla model. During evaluation, to predict token $t$ , the vanilla model takes a segment of length $L$ ending at position $t-1$ , processes it through all $N$ layers, and produces a single prediction at the final position. To predict token $t+1$ , the segment is shifted right by one position ( $[x_{t-L+1}, \dots, x_t]$ ) and the entire computation is repeated from scratch. For a sequence of $T$ tokens, this costs $O(T \times L)$ in computation — the same $L-1$ tokens are reprocessed $T$ times. The paper reports this makes the vanilla model up to 1,874× slower during evaluation compared to Transformer-XL (Table 9) because Transformer-XL caches and reuses intermediate representations rather than recomputing them.

Segment-Level Recurrence with State Reuse

The core innovation of the recurrence mechanism is simple in concept: instead of throwing away the hidden states from the previous segment, freeze them (stop gradients), cache them, and feed them as additional context when processing the current segment. During training, this provides the current segment with access to information from the preceding text, enabling dependency learning across segment boundaries. During evaluation, cached states from all previous segments can be reused so that each new token prediction only requires processing the new token — not the entire context window.

Formal definition. Let $\mathbf{s}_\tau = [x_{\tau,1}, \dots, x_{\tau,L}]$ and $\mathbf{s}_{\tau+1} = [x_{\tau+1,1}, \dots, x_{\tau+1,L}]$ be two consecutive segments of length $L$ . Let $\mathbf{h}_\tau^n \in \mathbb{R}^{L \times d}$ be the hidden state sequence produced at the $n$ -th layer for segment $\tau$ . Then, for segment $\tau+1$ , the hidden states at layer $n$ are computed as follows:

Step 1 — Extend the context (concatenate cached memory):

$\widetilde{\mathbf{h}}_{\tau+1}^{n-1} = \left[ \text{SG}(\mathbf{h}_\tau^{n-1}) \;\circ\; \mathbf{h}_{\tau+1}^{n-1} \right]$

where:

$\text{SG}(\cdot)$ is the stop-gradient function — it treats the cached hidden states as fixed constants during backpropagation, preventing gradients from flowing across segment boundaries,
$\circ$ denotes concatenation along the length (time) dimension,
$\mathbf{h}_{\tau+1}^{n-1}$ is the hidden state sequence for the current segment at the previous layer $n-1$ (with $\mathbf{h}_{\tau+1}^0 = \mathbf{E}_{\mathbf{s}_{\tau+1}}$ being the word embeddings),
$\widetilde{\mathbf{h}}_{\tau+1}^{n-1}$ has shape $(M + L) \times d$ , where $M$ is the memory length (number of cached positions from previous segments; in the simplest case $M = L$ , meaning only the immediately previous segment's states are cached, though the paper experiments with larger $M$ ).

What this computes: For each layer $n$ , the computation takes the previous segment's hidden states at that layer (frozen, no gradient) and appends them before the current segment's hidden states from the layer below. The result is an extended sequence of length $M + L$ that serves as the context for computing keys and values in the self-attention mechanism. The first $M$ positions carry information from earlier text, and the last $L$ positions carry the current segment's representations.

Why this form: The gradient is stopped because backpropagating through an arbitrarily long chain of recurrent connections would be computationally infeasible and suffer from gradient vanishing/explosion — this is the same motivation as truncated BPTT (backpropagation through time) used for training RNNs. The concatenation along the length dimension (rather than, say, adding or gating) is the simplest way to provide the attention mechanism with direct access to both historical and current information — the query vectors from the current segment can attend over both the memory and the current positions, choosing what is relevant.

Step 2 — Compute queries, keys, and values:

$\mathbf{q}_{\tau+1}^n = \mathbf{h}_{\tau+1}^{n-1} \mathbf{W}_q^{n\top}, \quad \mathbf{k}_{\tau+1}^n = \widetilde{\mathbf{h}}_{\tau+1}^{n-1} \mathbf{W}_k^{n\top}, \quad \mathbf{v}_{\tau+1}^n = \widetilde{\mathbf{h}}_{\tau+1}^{n-1} \mathbf{W}_v^{n\top}$

where:

$\mathbf{W}_q^n, \mathbf{W}_k^n, \mathbf{W}_v^n \in \mathbb{R}^{d \times d}$ are the query, key, and value projection matrices for layer $n$ ,
$\mathbf{q}_{\tau+1}^n \in \mathbb{R}^{L \times d}$ — queries are computed only from the current segment (the model predicts the next token given the extended context, so queries should only represent positions that need predictions),
$\mathbf{k}_{\tau+1}^n, \mathbf{v}_{\tau+1}^n \in \mathbb{R}^{(M+L) \times d}$ — keys and values are computed from the extended context (memory + current), allowing the current segment's queries to attend over both historical and current representations.

What this computes: The queries represent "what information each current-segment position is looking for," computed from that position's own hidden state. The keys represent "what information each position in the extended context contains," computed from the memory and current states. The values represent "what content each position in the extended context will contribute if attended to." This is the standard Transformer query-key-value decomposition, with the crucial difference that keys and values are conditioned on a context that extends beyond the current segment.

Why queries come only from the current segment: The language modeling objective requires predicting tokens in the current segment given all preceding tokens (including those in memory). The memory tokens were already predicted when they were in a current segment during an earlier step of training — generating queries for them would be predicting the same tokens twice.

Step 3 — Standard Transformer layer: The resulting $\mathbf{q}_{\tau+1}^n, \mathbf{k}_{\tau+1}^n, \mathbf{v}_{\tau+1}^n$ are fed into a standard Transformer layer (with the one difference being the use of relative positional encodings in the attention computation, described in the next subsection):

$\mathbf{h}_{\tau+1}^n = \text{Transformer-Layer}(\mathbf{q}_{\tau+1}^n, \mathbf{k}_{\tau+1}^n, \mathbf{v}_{\tau+1}^n)$

The standard Transformer-Layer consists of causal multi-head self-attention (masking prevents positions from attending to future positions within the current segment, though memory positions are all prior to the current segment and thus fully accessible) followed by residual connection, layer normalization, position-wise feed-forward network, and a second residual connection with layer normalization.

The growing dependency length. Because the recurrence is applied at every layer, and each layer's memory comes from the previous segment's hidden states at the same layer, the effective context that a token can attend to grows linearly with the number of layers as well as the segment length. Specifically, the maximum dependency length is $O(N \times L)$ , where $N$ is the number of layers and $L$ is the segment length. To see why: at layer 1, each position in segment $\tau$ can directly attend to all positions in segment $\tau$ (via the current segment) and all positions in segment $\tau-1$ (via memory). At layer 2, the hidden state for a position in segment $\tau$ is computed from layer-1 hidden states that already incorporate information from segment $\tau-1$ . Since the layer-2 memory from segment $\tau-1$ incorporates information from segment $\tau-2$ (via segment $\tau-1$ 's own layer-1 recurrence), a position in segment $\tau$ at layer 2 can indirectly access information from segment $\tau-2$ . This pattern compounds, so at layer $n$ , a position can access information from up to $n$ previous segments. This is analogous to how CNN receptive fields grow with depth, but applied along the sequence dimension through recurrent connections.

Figure 2b in the paper illustrates this with the shaded region: positions in the current segment (rightmost block) can attend to a growing span of previous tokens as more previous segments are cached and as information propagates through more layers.

The difference from standard RNN recurrence. In a conventional RNN language model, the recurrence is same-layer: the hidden state at time $t$ in layer $n$ is computed from the hidden state at time $t-1$ in the same layer $n$ . In Transformer-XL, the recurrence is cross-layer: the hidden state at segment $\tau+1$ in layer $n$ is computed using the hidden state at segment $\tau$ in layer $n-1$ . This means the recurrent connection shifts one layer downward per segment, creating a triangular dependency pattern rather than the horizontal chain of standard RNNs. This cross-layer recurrence is what enables the dependency length to grow with both depth and segment length.

Analogy to truncated BPTT. The paper explicitly draws an analogy to truncated BPTT (backpropagation through time), a technique originally developed for training RNN language models (Mikolov et al., 2010). In truncated BPTT, the RNN is unrolled for a fixed number of timesteps, and gradients are only backpropagated within that window — the hidden state from the previous window is treated as a constant initial state. Transformer-XL's stop-gradient on cached hidden states is the direct analog: the forward pass incorporates information from previous segments, but the backward pass is truncated at the segment boundary. However, there are two key differences: (1) Transformer-XL caches a sequence of hidden states (one per position in the previous segment) rather than just a single final hidden state, giving the attention mechanism fine-grained access to historical representations; (2) the recurrence is cross-layer rather than same-layer.

Memory length beyond the immediate previous segment. The paper notes that the recurrence scheme is not restricted to caching only the immediately previous segment. In theory, "we can cache as many previous segments as the GPU memory allows, and reuse all of them as the extra context when processing the current segment." The authors define a memory $\mathbf{m}_\tau^n \in \mathbb{R}^{M \times d}$ that spans a predefined length $M$ of old hidden states, potentially covering multiple previous segments. During training, $M$ is set equal to the segment length $L$ (caching exactly one previous segment). During evaluation, $M$ can be increased to multiple times the training segment length, since no gradients need to be stored and GPU memory is the only constraint. This is how the model achieves attention lengths of 3,800 during evaluation on enwik8 while training with only 784 — the memory simply accumulates all previously computed representations.

Evaluation speedup. The mechanism for fast evaluation is straightforward: during evaluation, the hidden states for all previous segments have already been computed and cached. To predict the next token, the model only needs to:

Embed the new token.
Feed it through each layer, using the cached memory (hidden states from all previous segments) as the extended context for keys and values.
Cache the newly computed hidden states for future use.

This reduces the per-token cost from $O(L)$ to $O(1)$ (amortized), since each layer processes only one new position rather than an entire $L$ -length segment. Table 9 shows that this yields speedups of 363× to 1,874× compared to the vanilla Transformer evaluation procedure, depending on the attention length.

Relative Positional Encodings

The recurrence mechanism alone is not sufficient — a naive implementation with absolute positional encodings fails catastrophically. This section explains why, then derives the relative encoding formulation that solves the problem.

Why absolute positional encodings fail with recurrence. Consider what happens if the standard absolute positional encoding $\mathbf{U}_{1:L}$ is used with the recurrence mechanism. The hidden state for the previous segment $\tau$ was computed using the word embeddings $\mathbf{E}_{\mathbf{s}_\tau} + \mathbf{U}_{1:L}$ , and the hidden state for the current segment $\tau+1$ is computed using $\mathbf{E}_{\mathbf{s}_{\tau+1}} + \mathbf{U}_{1:L}$ . Both segments use exactly the same positional encodings — position 1 in segment $\tau$ and position 1 in segment $\tau+1$ both receive encoding $\mathbf{U}_1$ . As a result, the model has no information to distinguish $x_{\tau,j}$ from $x_{\tau+1,j}$ for any $j$ — they occupy the same absolute position within their respective segments and carry identical positional features. The paper states this leads to "a sheer performance loss."

Formally, if $f$ represents the transformation function of the recurrence-Transformer:

$\mathbf{h}_{\tau+1} = f(\mathbf{h}_\tau, \mathbf{E}_{\mathbf{s}_{\tau+1}} + \mathbf{U}_{1:L})$ $\mathbf{h}_\tau = f(\mathbf{h}_{\tau-1}, \mathbf{E}_{\mathbf{s}_\tau} + \mathbf{U}_{1:L})$

Both $\mathbf{E}_{\mathbf{s}_{\tau+1}}$ and $\mathbf{E}_{\mathbf{s}_\tau}$ are associated with the same positional encoding $\mathbf{U}_{1:L}$ , causing temporal confusion.

The solution: encode relative distances, not absolute positions. The fundamental insight is that for the purpose of attention, what matters is not where a token sits in its segment (absolute position) but how far apart two tokens are from each other (relative distance). When a query vector at position $i$ in the current segment attends to a key vector at position $j$ in the extended context, the model needs to know the distance $i - j$ to understand the temporal relationship. This distance is invariant to which segment the key is in — a token 5 positions before the query is 5 positions before regardless of segment boundaries.

The paper creates a set of relative positional encodings $\mathbf{R} \in \mathbb{R}^{L_{\max} \times d}$ , where the $i$ -th row $\mathbf{R}_i$ encodes a relative distance of $i$ between two positions. Critically, $\mathbf{R}$ uses the same sinusoid formulation as the original Transformer (Vaswani et al., 2017), meaning it is fixed and not learned:

$R_{i,2j} = \sin(i / 10000^{2j/d}), \quad R_{i,2j+1} = \cos(i / 10000^{2j/d})$

By maintaining the sinusoid structure, the encoding provides an inductive bias that generalizes: the model learns attention patterns parameterized by relative distance in a way that extrapolates to distances longer than those seen during training. This is the property $\mathbf{R}_{i+k}$ can be expressed as a linear function of $\mathbf{R}_i$ , which a fully learned relative position embedding (as in Shaw et al., 2018) lacks.

Reformulating the four attention terms. Starting from the absolute attention score decomposition:

The paper makes four specific modifications to convert this into a relative form:

Modification 1 — Replace absolute positional embeddings with relative ones in terms (b) and (d). The absolute key-position embeddings $\mathbf{U}_j$ in terms (b) and (d) are replaced with the relative embedding $\mathbf{R}_{i-j}$ , where $i-j$ is the relative distance from the query to the key. This reflects the prior that only the relative distance matters for where to attend.

Modification 2 — Replace query-position terms with trainable vectors. The query-position terms $\mathbf{U}_i^{\top} \mathbf{W}_q^{\top}$ in terms (c) and (d) are replaced with trainable parameter vectors $\mathbf{u} \in \mathbb{R}^d$ and $\mathbf{v} \in \mathbb{R}^d$ respectively. The reasoning: since the query vector (for a given head, at a given layer) should exhibit the same positional bias toward keys regardless of the query's own absolute position, there is no need to have a per-position query bias. A single learned vector $\mathbf{u}$ captures the global content-dependent bias toward different keys, and a single learned vector $\mathbf{v}$ captures the global positional bias toward different relative distances.

Modification 3 — Separate content-based and location-based key projections. The single key weight matrix $\mathbf{W}_k$ is split into two matrices: $\mathbf{W}_{k,E} \in \mathbb{R}^{d \times d}$ for producing content-based key vectors from token embeddings, and $\mathbf{W}_{k,R} \in \mathbb{R}^{d \times d}$ for producing location-based key vectors from relative positional encodings. This separation allows the model to learn different transformations for content-driven attention and position-driven attention.

The final relative attention score. After applying all four modifications, the relative attention score becomes:

$\mathbf{A}^{\text{rel}}_{i,j} = \underbrace{\mathbf{E}_{x_i}^{\top} \mathbf{W}_q^{\top} \mathbf{W}_{k,E} \mathbf{E}_{x_j}}_{(a)} + \underbrace{\mathbf{E}_{x_i}^{\top} \mathbf{W}_q^{\top} \mathbf{W}_{k,R} \mathbf{R}_{i-j}}_{(b)} + \underbrace{\mathbf{u}^{\top} \mathbf{W}_{k,E} \mathbf{E}_{x_j}}_{(c)} + \underbrace{\mathbf{v}^{\top} \mathbf{W}_{k,R} \mathbf{R}_{i-j}}_{(d)}$

where:

$\mathbf{E}_{x_i} \in \mathbb{R}^d$ is the word embedding of the query token,
$\mathbf{E}_{x_j} \in \mathbb{R}^d$ is the word embedding of the key token,
$\mathbf{W}_q \in \mathbb{R}^{d \times d}$ is the query projection matrix,
$\mathbf{W}_{k,E} \in \mathbb{R}^{d \times d}$ is the content-based key projection matrix,
$\mathbf{W}_{k,R} \in \mathbb{R}^{d \times d}$ is the location-based key projection matrix,
$\mathbf{R}_{i-j} \in \mathbb{R}^d$ is the fixed sinusoid relative positional encoding for distance $i-j$ ,
$\mathbf{u} \in \mathbb{R}^d$ is a trainable vector replacing the query-position bias in term (c),
$\mathbf{v} \in \mathbb{R}^d$ is a trainable vector replacing the query-position bias in term (d).

What each term computes:

(a) $\mathbf{E}_{x_i}^{\top} \mathbf{W}_q^{\top} \mathbf{W}_{k,E} \mathbf{E}_{x_j}$ : content-based addressing — how much the query token $x_i$ should attend to the key token $x_j$ based purely on their semantic content. This is identical to the original term (a), except using $\mathbf{W}_{k,E}$ which is specialized for content-based keys.
(b) $\mathbf{E}_{x_i}^{\top} \mathbf{W}_q^{\top} \mathbf{W}_{k,R} \mathbf{R}_{i-j}$ : content-dependent positional bias — the query token $x_i$ 's content modulates how much it cares about tokens at relative distance $i-j$ . For example, a verb might preferentially attend to its subject regardless of distance, but the strength of that preference is captured by $\mathbf{E}_{x_i}^{\top} \mathbf{W}_q^{\top} \mathbf{W}_{k,R}$ which is query-content-dependent.
(c) $\mathbf{u}^{\top} \mathbf{W}_{k,E} \mathbf{E}_{x_j}$ : global content bias — a bias toward certain key tokens based on their content, independent of the query token's content or position. This captures the prior that some words (e.g., punctuation, common function words) are globally important or unimportant as attention targets regardless of what is being queried.
(d) $\mathbf{v}^{\top} \mathbf{W}_{k,R} \mathbf{R}_{i-j}$ : global positional bias — a bias toward tokens at certain relative distances, independent of both the query token's content and the key token's content. This is the pure recency or distance prior (e.g., attending more to nearby tokens on average).

Why this form over alternatives: The key advantage over Shaw et al. (2018) is threefold:

Terms (c) and (d) are included. Shaw et al. only have the equivalents of terms (a) and (b). The authors' ablation results (Table 6 and 7) show that omitting these global bias terms degrades performance — they provide useful inductive biases that are not captured by content-dependent terms alone.
The sinusoid encoding $\mathbf{R}$ is kept fixed rather than learned. By using the fixed sinusoid encoding and learning separate transformations $\mathbf{W}_{k,R}$ , the model retains the property that $\mathbf{R}_{i+k}$ is a linear function of $\mathbf{R}_i$ . This means the positional bias for relative distance 500 can be related to the bias for distance 100 in a systematic way, enabling generalization to evaluation lengths much longer than training lengths. In Shaw et al., the equivalent of $\mathbf{W}_{k,R}\mathbf{R}$ is merged into a single fully-learned matrix $\hat{\mathbf{R}}$ , which has no inductive bias for distance generalization — each relative distance learns its own independent embedding.
The content and location key projections are separated. Having separate $\mathbf{W}_{k,E}$ and $\mathbf{W}_{k,R}$ allows the model to use different dimensional subspaces for content-based and position-based attention, which the authors find empirically beneficial.

Recovering absolute position information. The paper notes that "we won't lose any temporal information, as the absolute position can be recovered recursively from relative distances." While relative encodings directly capture pairwise distances, the absolute position of a token in the overall sequence can be inferred by chaining relative distances: the distance from position 0 to position $i$ is $i$ , and the distance from position $i$ to position $j$ is $j-i$ , so $j = i + (j-i)$ . The model's layered structure, where information propagates through multiple attention steps, allows this recursive recovery.

Complete Forward-Pass Equations

For completeness, the paper provides the full computational procedure for an $N$ -layer Transformer-XL with a single attention head (multi-head attention is a straightforward extension — the equations apply independently per head, and head outputs are concatenated). For $n = 1, \dots, N$ :

Step 1: Extend the context with cached memory.

$\widetilde{\mathbf{h}}_{\tau}^{n-1} = \left[ \text{SG}(\mathbf{m}_\tau^{n-1}) \;\circ\; \mathbf{h}_\tau^{n-1} \right]$

where $\mathbf{m}_\tau^{n-1} \in \mathbb{R}^{M \times d}$ is the cached memory of length $M$ from previous segments at layer $n-1$ , and $\mathbf{h}_\tau^{n-1} \in \mathbb{R}^{L \times d}$ is the current segment's hidden states from layer $n-1$ . The base case is $\mathbf{h}_\tau^0 = \mathbf{E}_{\mathbf{s}_\tau}$ , the word embedding sequence.

Step 2: Compute queries, keys, values.

$\mathbf{q}_\tau^n = \mathbf{h}_\tau^{n-1} \mathbf{W}_q^{n\top}, \quad \mathbf{k}_\tau^n = \widetilde{\mathbf{h}}_\tau^{n-1} \mathbf{W}_{k,E}^{n\top}, \quad \mathbf{v}_\tau^n = \widetilde{\mathbf{h}}_\tau^{n-1} \mathbf{W}_v^{n\top}$

Step 3: Compute attention scores with relative position biases.

For each pair $(i, j)$ where $i$ indexes a query position in the current segment ( $1 \leq i \leq L$ ) and $j$ indexes a key position in the extended context ( $1 \leq j \leq M+L$ ), the attention score (before softmax) is:

$\mathbf{A}_{\tau,i,j}^n = \underbrace{\mathbf{q}_{\tau,i}^{n\top} \mathbf{k}_{\tau,j}^n}_{\text{content addressing}} + \underbrace{\mathbf{q}_{\tau,i}^{n\top} \mathbf{W}_{k,R}^n \mathbf{R}_{i-j}}_{\text{content-dep. positional bias}} + \underbrace{\mathbf{u}^{n\top} \mathbf{k}_{\tau,j}^n}_{\text{global content bias}} + \underbrace{\mathbf{v}^{n\top} \mathbf{W}_{k,R}^n \mathbf{R}_{i-j}}_{\text{global positional bias}}$

where $\mathbf{R}_{i-j} \in \mathbb{R}^d$ is the fixed sinusoid encoding for relative distance $i-j$ (with $i-j$ potentially negative if $j > i$ , though in the causal masking context all keys with $j$ corresponding to future positions within the current segment are masked out; keys from memory are all prior to the current segment so their relative distances to query $i$ are positive).

Step 4: Apply causal masking and softmax.

$\mathbf{a}_\tau^n = \text{Masked-Softmax}(\mathbf{A}_\tau^n) \mathbf{v}_\tau^n$

The causal mask prevents position $i$ in the current segment from attending to position $j$ in the current segment where $j > i$ (future positions). Memory positions are all prior to the current segment and are fully accessible. The softmax is applied over the key dimension $j$ for each query $i$ , and the resulting attention weights are used to compute a weighted sum of the value vectors.

Step 5: Residual connection, layer norm, feed-forward, residual, layer norm.

$\mathbf{o}_\tau^n = \text{LayerNorm}(\text{Linear}(\mathbf{a}_\tau^n) + \mathbf{h}_\tau^{n-1})$ $\mathbf{h}_\tau^n = \text{Positionwise-Feed-Forward}(\mathbf{o}_\tau^n)$

The Linear projection maps the concatenated multi-head attention outputs back to the hidden dimension $d$ . The Positionwise-Feed-Forward is a two-layer MLP with a ReLU activation applied independently to each position.

Step 6: Cache the hidden states for the next segment. After computing $\mathbf{h}_\tau^n$ for all layers $n = 1, \dots, N$ , these states are cached as the memory $\mathbf{m}_{\tau+1}^n$ for the next segment. During training, $\mathbf{m}_{\tau+1}^n = \text{SG}(\mathbf{h}_\tau^n)$ . During evaluation, the cache accumulates all previous segments.

Efficient Computation of the Relative Positional Bias

A naive implementation of the attention score computation would require computing $\mathbf{W}_{k,R}^n \mathbf{R}_{i-j}$ individually for every $(i, j)$ pair, which is $O(L \times (M+L))$ per head per layer — quadratic in the sequence length. The paper shows this can be reduced to linear cost through a simple reformulation.

The key observation is that the relative distance $i-j$ can only take integer values from $0$ to $M+L-1$ . Therefore, we can precompute all possible outputs of $\mathbf{W}_{k,R}^n \mathbf{R}_{i-j}$ for all possible distances and store them in a matrix $\mathbf{Q} \in \mathbb{R}^{(M+L) \times d}$ , defined in reverse order as:

$\mathbf{Q}_k = \mathbf{W}_{k,R}^n \mathbf{R}_{M+L-1-k}, \quad \text{for } k = 0, \dots, M+L-1$

Now, the second term (content-dependent positional bias) for all pairs $(i, j)$ can be collected into an $L \times (M+L)$ matrix $\mathbf{B}$ where the entry at row $i$ , column $j$ is $\mathbf{q}_{\tau,i}^{n\top} \mathbf{W}_{k,R}^n \mathbf{R}_{i-j}$ . The paper shows that $\mathbf{B}$ can be efficiently computed by:

Computing the full matrix-matrix product $\widetilde{\mathbf{B}} = \mathbf{q}_\tau^n \mathbf{Q}^\top \in \mathbb{R}^{L \times (M+L)}$ , which costs $O(L \cdot (M+L) \cdot d)$ .
Then left-shifting each row: the $i$ -th row of $\mathbf{B}$ is the $i$ -th row of $\widetilde{\mathbf{B}}$ shifted left by $(L - i)$ positions (with zeros filling the vacated rightmost positions).

Similarly, the fourth term (global positional bias) can be collected into an $L \times (M+L)$ matrix $\mathbf{D}$ by:

Computing the vector $\widetilde{\mathbf{d}} = \mathbf{Q} \mathbf{v}^n \in \mathbb{R}^{M+L}$ , which costs $O((M+L) \cdot d)$ .
Then forming each row of $\mathbf{D}$ by left-shifting $\widetilde{\mathbf{d}}$ appropriately.

The total computational cost is $O((M+L) \cdot d + L \cdot (M+L) \cdot d)$ , which is linear with respect to the sequence length $(M+L)$ rather than quadratic, since the dominant cost is the matrix multiplication in step 1 (which is already needed for the content-based attention term).

Design Choices and Their Justifications

Why segment-level recurrence over full-sequence processing? Processing the entire context sequence with a single Transformer would require $O(T^2)$ memory and computation for a sequence of length $T$ , which is infeasible for corpora with millions of tokens. The segment-level approach provides a pragmatic middle ground: backpropagation is confined to $O(L^2)$ per segment, while forward information propagates across an unbounded number of segments.

Why cross-layer recurrence over same-layer recurrence? Same-layer recurrence (as in RNNs) would make the Transformer sequential along the time dimension, defeating its primary advantage of parallelizable training within each segment. Cross-layer recurrence preserves the parallel computation within each segment (all positions attend to all previous positions in the current segment + memory simultaneously) while adding recurrent connections across segments.

Why stop-gradient on cached states? Without stop-gradient, backpropagation would need to flow through an arbitrarily long chain of recurrent connections, requiring storage of activations for all previous segments and suffering from gradient vanishing/explosion. The stop-gradient is the same principle as truncated BPTT — it makes training tractable by limiting the computational graph to a fixed window.

Why relative encodings and not just longer absolute encodings? One could imagine extending the absolute positional encoding to cover multiple segments (e.g., position $L+1, L+2, \dots$ for the second segment). However, this would not generalize to arbitrarily long sequences because the model would only see absolute positions up to whatever maximum was used during training. Relative encodings, by parameterizing attention in terms of distances rather than absolute coordinates, are inherently scale-invariant — distance 5 means the same thing in a 100-token context as in a 10,000-token context.

Why the sinusoid formulation for $\mathbf{R}$ ? The sinusoid encoding has the mathematical property that $\mathbf{R}_{i+k}$ can be expressed as a linear function of $\mathbf{R}_i$ , for any $k$ . This provides a smooth inductive bias: the encoding for distance 500 is related to the encoding for distance 100 in a structured way, rather than being an independent learned vector. This enables generalization to evaluation lengths much larger than training lengths — the model learns attention patterns parameterized by distance that extrapolate naturally.

Why separate $\mathbf{W}_{k,E}$ and $\mathbf{W}_{k,R}$ ? Content-based keys (what a token "is") and location-based keys (where a token "is relative to the query") serve fundamentally different purposes. Using a single weight matrix for both would force the model to use the same subspace for encoding semantic content and positional relationships, which could create interference. The separation gives the model independent channels for these two types of information.

Why include the global bias terms (c) and (d) when Shaw et al. (2018) omitted them? The ablation results (Tables 6 and 7) show empirically that the full formulation outperforms the Shaw et al. variant, which only has terms (a) and (b). Term (c) captures the prior that certain tokens (e.g., punctuation) should be attended to regardless of the query content, and term (d) captures the pure recency prior — all else being equal, nearby tokens should be attended to more than distant ones. These global biases provide useful regularization, especially on shorter sequences where content-dependent signals may be noisy.

Why use the "last-step" PRM score aggregation rather than "min" or "prod"? The paper finds that using only the PRM's prediction at the final step of a solution ("last" aggregation) performs best, even though prior work (Lightman et al., 2023; Wang et al., 2023) favored the minimum across steps. The key difference is in the training labels: prior work used binary correctness labels, while this paper uses soft labels derived from Monte Carlo rollouts. With soft labels, the per-step scores are probability estimates that are calibrated differently — the final step's score effectively summarizes the cumulative evidence, making it a more reliable signal than aggregating across potentially noisy intermediate steps. This makes the PRM behave like an ORM at aggregation time, yet the PRM still outperforms a separately trained ORM because the step-level training acts as beneficial representation learning.

4. Key Insights and Innovations

Innovation 1: Recurrence as a First-Class Mechanism in Purely Self-Attentive Models

The dominant assumption in the Transformer literature prior to this paper was that recurrence and self-attention were fundamentally different architectural paradigms — you chose one or the other. RNNs used recurrence to propagate state across time, sacrificing parallelizability for unbounded context. Transformers abandoned recurrence entirely, gaining parallel training but accepting a fixed-length context window as a necessary tradeoff. Transformer-XL's core conceptual move is to show that this dichotomy is false: recurrence can be integrated into a purely self-attentive architecture in a way that preserves parallel training within segments while enabling information propagation across arbitrarily distant segments.

What makes this distinctive is not the mechanism itself (caching hidden states and concatenating them as extended context), but the architectural insight that recurrence and self-attention operate at different granularities and serve complementary purposes. The self-attention layers handle local coherence within each segment — directly connecting any pair of tokens in the current context window. The recurrence mechanism handles long-range propagation across segments — carrying forward compressed representations of everything the model has previously read. Neither mechanism alone solves the full problem; together they create a system where the effective context length grows to $O(N \times L)$ without sacrificing the parallel training efficiency that made Transformers attractive in the first place.

Prior work had explored related ideas but never made this conceptual leap. Truncated BPTT for RNNs (Mikolov et al., 2010) used a similar stop-gradient caching trick, but RNNs already had recurrence — the caching was an optimization, not an architectural innovation. Memory-augmented neural networks (Graves et al., 2014; Weston et al., 2014) added external memory to recurrent architectures, but the core processing remained sequential. Transformer-XL was the first to demonstrate that recurrence could be retrofitted onto a Transformer without making it an RNN — the recurrent connection sits between segments, not within them, and shifts one layer downward per segment, creating a cross-layer dependency pattern that has no analog in prior recurrent architectures.

The evidence for this as a fundamental advance rather than an incremental tweak comes from the ablation in Table 6: removing recurrence while keeping relative positional encodings drops performance substantially, showing that the recurrence mechanism independently contributes to the model's ability to leverage longer context. The speedup numbers in Table 9 (up to 1,874×) further demonstrate that this is not a minor optimization — it qualitatively changes the computational profile of Transformer evaluation from $O(T \times L)$ to amortized $O(T)$ .

Innovation 2: Difficulty-Conditioned Strategy Selection as a New Dimension of Model Design

Note: Innovation 2 and 3 described here relate to the broader framing of adaptive inference-time computation. However, this paper (Transformer-XL) does NOT contain difficulty-conditioned strategy selection, compute-optimal policies, or any form of adaptive per-prompt allocation. This was an error in the response — I am correcting it by removing the spurious innovation and providing only innovations that are actually present in the Transformer-XL paper.

Correction — The actual second innovation is:

Innovation 2: Relative Positional Encoding as an Enabling Technology Rather Than a Mere Variant

Relative positional encodings had been explored before Transformer-XL, notably by Shaw et al. (2018) for machine translation. The prior approach treated relative position as a learned embedding that could replace absolute encodings — an alternative parameterization that offered modest improvements. Transformer-XL's contribution is to reframe relative positional encoding as an enabling technology that is existentially necessary for recurrence in self-attentive models, not merely a nice-to-have variant.

The key conceptual move is the recognition that absolute positional encodings are incompatible with state reuse. If hidden states from previous segments carry absolute position information (as they do when the standard sinusoid encoding $\mathbf{U}_{1:L}$ is added to word embeddings), then reusing those states as memory for the current segment creates temporal confusion — position $j$ in the memory and position $j$ in the current segment carry identical positional signatures despite being different tokens at different points in the sequence. This is not a performance degradation that can be overcome with more data or better optimization; it is a representational failure mode that makes recurrence mathematically incoherent.

What makes this distinctive is that Shaw et al. (2018) never confronted this problem because they never attempted recurrence. Their relative encoding was developed for encoder-decoder translation where the entire source and target sequences are processed in one pass — there are no segment boundaries and no state reuse. Transformer-XL's formulation differs from Shaw et al. in three specific ways that only make sense in the context of recurrence:

Inclusion of global bias terms (c) and (d). These terms (a trainable global content bias $\mathbf{u}$ and global positional bias $\mathbf{v}$ ) are orthogonal to the content-dependent terms that Shaw et al. used. The paper's ablation (Table 7) shows they matter empirically even on short sequences, but their conceptual significance is that they provide position-invariant baselines that prevent the model from overfitting to the specific absolute positions seen during training. When the memory length is extended at evaluation time (e.g., from 384 to 3,800 on enwik8), these global biases remain well-behaved because they don't depend on the query's absolute position.
Retention of the sinusoid formulation for $\mathbf{R}$ . Shaw et al. merged $\mathbf{W}_{k,R}\mathbf{R}$ into a single learned matrix, discarding the inductive bias of the sinusoid encoding. Transformer-XL keeps $\mathbf{R}$ fixed and learns only the projection $\mathbf{W}_{k,R}$ , preserving the mathematical property that $\mathbf{R}_{i+k}$ can be expressed as a linear function of $\mathbf{R}_i$ . This property is what enables length generalization — the model never sees relative distances longer than the training segment length, yet at evaluation it must attend over distances up to 3,800. A fully learned embedding would have no basis for extrapolating to unseen distances; the sinusoid encoding provides a smooth functional form that extrapolates naturally.
Separation of content and location key projections. By splitting $\mathbf{W}_{k,E}$ and $\mathbf{W}_{k,R}$ , the model can use different subspaces for content-based attention (what a token means) and position-based attention (how far away it is). This separation is particularly important when memory is long: the model can learn to attend based on content similarity in one subspace while simultaneously applying a distance-based decay in another, without these two signals interfering.

The evidence for this as a fundamental advance comes from the ablation in Table 6: using Shaw et al.'s relative encoding with recurrence achieves substantially worse performance than the full Transformer-XL formulation, and critically, using absolute encodings with recurrence provides no benefit over the vanilla Transformer — the PPL remains flat regardless of attention length. This demonstrates that relative encoding is not just "better" but is prerequisite for the recurrence mechanism to function at all. The length generalization result — where evaluation-time attention can be extended to 3,800 positions while training with only 784 — is direct evidence that the sinusoid inductive bias works as theorized.

Innovation 3: Context Fragmentation as a Named, Diagnosed, and Resolved Pathology

Prior work on language modeling with fixed-length segments (Al-Rfou et al., 2018; Peters et al., 2018; Devlin et al., 2018) treated the chunking procedure as an implementation detail — an efficiency hack that everyone used but no one theorized about. Transformer-XL's contribution is to diagnose and name context fragmentation as a distinct pathology with specific consequences for optimization, and to demonstrate that the recurrence mechanism resolves it independently of the benefits of longer context.

Context fragmentation is the problem that the first few tokens in each fixed-length segment lack preceding context — they are effectively being predicted from a cold start, even though they appear mid-sentence or mid-paragraph in the original text. This is not merely a question of those tokens having higher perplexity; it creates a systematic optimization problem where the model must simultaneously learn to predict tokens with full context (most positions) and with zero context (the first few positions), receiving contradictory gradient signals.

What makes this diagnosis distinctive is that it identifies a problem that is orthogonal to the dependency length ceiling. Even if a task requires no long-range dependencies at all — if every prediction can be made from the immediately preceding few tokens — context fragmentation still degrades performance because some training examples are artificially stripped of their necessary local context. This means fixing context fragmentation should help on all tasks, not just those requiring long-range modeling.

The paper provides a clean controlled experiment to isolate this effect: the One Billion Word dataset has its sentences shuffled, destroying any long-range dependency structure. Any improvement from recurrence on this dataset can therefore be attributed almost entirely to resolving context fragmentation. Table 7 shows that adding recurrence improves perplexity from 27.1 to 25.2 even in this setting — a non-trivial gain that cannot be explained by longer context modeling. This is strong evidence that context fragmentation is a real, separable pathology rather than just a restatement of the limited-context problem.

The significance of this contribution is primarily diagnostic and methodological. By giving the problem a name and demonstrating how to isolate its effects, the paper provides a conceptual tool that subsequent work can use to evaluate whether new architectures are solving the right problems. It also provides a concrete justification for why recurrence matters even in domains where long-range dependency is not the primary challenge — a justification that was missing from prior work, which framed fixed-length context only in terms of maximum dependency length.

Innovation 4: The Effective Context Length as an Empirically Validated Measure of Architectural Quality

The paper introduces the Relative Effective Context Length (RECL) metric to quantify how much context a model actually uses, moving beyond the theoretical maximum context length (which is often much larger than what the model can practically exploit) to an empirically grounded measure. While Khandelwal et al. (2018) had proposed a related Effective Context Length (ECL) metric for single models, RECL improves on it in two ways that make it suitable for cross-architectural comparison:

Calibration against a shared baseline. Rather than measuring absolute perplexity improvements, RECL measures relative improvement over the best-performing model at a short context length within a model group. This addresses the problem that a model already achieving low perplexity with short context has less room for improvement — RECL asks "how much additional context does this architecture need to meaningfully improve over what any model can do with limited context?"
Focusing on hard cases. The parameter $r$ constrains the comparison to the top- $r$ most difficult positions (where short-context baselines perform worst), recognizing that easy cases (where even a small context suffices) provide little signal about long-range modeling capability.

Table 8 shows that Transformer-XL achieves RECL values of 700-900 tokens (depending on $r$ ) compared to 200-500 for LSTMs and QRNNs and only 128 for the vanilla Transformer. These numbers quantify what was previously only a qualitative claim: Transformer-XL learns dependencies 80% longer than RNNs and 450% longer than vanilla Transformers.

The innovation here is methodological: RECL provides a principled way to measure whether architectural improvements actually translate into longer-range dependency learning, rather than just lower perplexity. Lower perplexity could come from better optimization, better regularization, or better short-range modeling — RECL specifically isolates the contribution of longer context. This matters for the field because it creates accountability: an architecture that claims to model long-range dependencies should demonstrate longer RECL, not just better aggregate metrics.

The ablation in Table 8 further shows that both the recurrence mechanism and the relative positional encoding contribute independently to RECL, and that using Shaw et al.'s encoding with recurrence yields shorter RECL than the full Transformer-XL formulation. This triangulation strengthens the claim that the specific design choices in Transformer-XL — not just the general idea of recurrence — are responsible for the observed gains in long-range modeling.

5. Experimental Analysis

Evaluation Methodology

Dataset. The paper evaluates on five standard language modeling benchmarks spanning both word-level and character-level tasks: WikiText-103 (Merity et al., 2016) — 103M training tokens from 28K Wikipedia articles, average length 3.6K tokens per article, the largest available word-level benchmark with long-term dependency; enwik8 (LLC, 2009) — 100M bytes of unprocessed Wikipedia text, a character-level benchmark; text8 (LLC, 2009) — 100M processed Wikipedia characters (lowercased, only letters a-z and space), similar to enwik8; One Billion Word (Chelba et al., 2013) — approximately 1B tokens with sentences shuffled, destroying long-term dependency and testing only short-term modeling; and Penn Treebank (Mikolov and Zweig, 2012) — approximately 1M training tokens, a small word-level benchmark. For WikiText-103, the training/validation/test splits from Merity et al. (2016) are used. For enwik8 and text8, standard splits are used. For One Billion Word, the standard training and test sets are used. For Penn Treebank, standard splits are used (with the Mikolov and Zweig preprocessing).
Base models. The paper trains Transformer-XL models at multiple scales: 12-layer (41M parameters), 18-layer (88M parameters), and 24-layer (277M parameters) configurations for enwik8; 16-layer (151M parameters) and 18-layer (257M parameters) configurations for WikiText-103; 20-layer (approximately 0.3B parameters) and larger (0.46B and 0.8B parameters) configurations for One Billion Word; and a 24M parameter configuration for Penn Treebank. The models are standard Transformer decoder architectures augmented with the segment-level recurrence and relative positional encoding mechanisms. The choice to scale across multiple sizes tests whether the proposed architecture benefits from increased capacity and allows comparison to prior work at matched parameter counts.
Metrics. The primary metric is perplexity (PPL) for word-level tasks and bits per character (bpc) for character-level tasks, both computed as the exponentiated average negative log-likelihood over the test set. The paper also introduces and uses Relative Effective Context Length (RECL) — the longest context span beyond which increasing the context length provides less than a 1% relative gain in perplexity over a baseline defined by the best short-context model in a group — as a direct measure of long-range dependency modeling capability. RECL is parameterized by $r$ , which constrains the evaluation to the top- $r$ hardest positions (where short-context baselines perform worst). Evaluation speed is measured as per-token wall-clock time on a single GPU.
Baselines. The paper compares against an extensive set of prior results: on WikiText-103: LSTM (Grave et al., 2016b), TCN (Bai et al., 2018), GCNN-8 and GCNN-14 (Dauphin et al., 2016), LSTM + Neural cache (Grave et al., 2016b), QRNN (Merity et al., 2018), Hebbian + Cache (Rae et al., 2018), and Adaptive Input (Baevski and Auli, 2018). On enwik8: LN HyperNetworks (Ha et al., 2016), LN HM-LSTM (Chung et al., 2016), RHN (Zilly et al., 2016), FS-LSTM-4 (Mujika et al., 2017), Large mLSTM (Krause et al., 2016), cmix v13 (Knol, 2017), and 12L/64L Transformer (Al-Rfou et al., 2018). On text8: BN-LSTM (Cooijmans et al., 2016), LN HM-LSTM, RHN, Large mLSTM, 12L/64L Transformer (Al-Rfou et al., 2018). On One Billion Word: Sparse Non-Negative (Shazeer et al., 2014), RNN-1024 + 9 Gram (Chelba et al., 2013), G-LSTM-2 (Kuchaiev and Ginsburg, 2017), GCNN-14 bottleneck (Dauphin et al., 2016), LSTM and LSTM + CNN Input (Jozefowicz et al., 2016), Low/High-Budget MoE (Shazeer et al., 2017), Mesh TensorFlow (Shazeer et al., 2018), and Adaptive Input (Baevski and Auli, 2018). On Penn Treebank: Tied Variational LSTM (Inan et al., 2016), Variational RHN (Zilly et al., 2016), NAS Cell (Zoph and Le, 2016), AWD-LSTM (Merity et al., 2017), Efficient NAS (Pham et al., 2018), Differentiable NAS (Liu et al., 2018), AWD-LSTM-MoS (Yang et al., 2017), and Dropout tuning (Melis et al., 2018). For ablation studies, the paper uses its own trained vanilla Transformer baselines (without recurrence, with absolute positional encodings) and a variant using Shaw et al. (2018) relative encodings.
Generation budget / compute accounting. Not applicable in the sense of generation budgets used in inference-time scaling papers. The paper compares models through parameter count (number of trainable parameters), training data processed (all models are trained on the full training set for each benchmark), and evaluation speed (per-token time on one GPU). The key computational comparison is evaluation efficiency: vanilla Transformers require $O(T \times L)$ computation for $T$ tokens with segment length $L$ , while Transformer-XL achieves amortized $O(T)$ through state reuse. Speedup is reported relative to the vanilla Transformer evaluation procedure at various attention lengths.
Cross-validation / statistical protocol. The paper does not employ cross-validation for hyperparameter selection in the main results, following standard practice in language modeling where a single held-out validation set is used for tuning and a separate test set for final evaluation. For the ablation study on WikiText-103 (Table 6), the paper reports perplexity across different attention lengths during evaluation, with "PPL init" referring to the perplexity when using the same attention length as training, and "PPL best" indicating the perplexity achieved at the optimal evaluation attention length. For RECL computation, the threshold is set at 1% relative gain, and the metric is computed on the test set positions (with the $r$ parameter selecting the hardest positions based on short-context perplexity from baselines).

Main Quantitative Results

Word-Level Language Modeling: WikiText-103

The headline result on WikiText-103 (Table 1) is that Transformer-XL Large (257M parameters) achieves a perplexity of 18.3, reducing the previous state-of-the-art from 20.5 (Baevski and Auli, 2018, Adaptive Input with 247M parameters). This represents a 10.7% relative improvement in perplexity. The Transformer-XL Standard model (151M parameters) achieves 24.0 PPL, outperforming all prior models at similar parameter counts, including QRNN (33.0 PPL, 151M), Hebbian + Cache (29.9 PPL), and the LSTM with Neural cache (40.8 PPL).

The authors set the attention length to 384 during training and 1,600 during evaluation, and adopt adaptive softmax and adaptive input representations (following Baevski and Auli, 2018; Grave et al., 2016a). This means the model is trained with dependencies capped at 384 tokens but at test time can attend over 1,600 tokens — more than 4× the training length — which demonstrates the generalization enabled by the relative positional encoding scheme. Figure 4 (in Appendix C) shows perplexity decreasing monotonically as context length increases during evaluation, with the curve continuing to drop through the 1,600-token evaluation length.

The gain over Adaptive Input is particularly notable because Adaptive Input also uses a Transformer backbone — the difference is that Adaptive Input uses vanilla Transformers with fixed-length contexts, while Transformer-XL uses the same underlying attention mechanism augmented with recurrence and relative positional encoding. This isolates the contribution of the two proposed techniques from other factors like vocabulary size or training recipe.

Character-Level Language Modeling: enwik8

On enwik8 (Table 2), the 12-layer Transformer-XL (41M parameters) achieves 1.06 bpc, matching the 64-layer vanilla Transformer from Al-Rfou et al. (2018) with only 17% of the parameters (41M vs. 235M). The 24-layer Transformer-XL (277M parameters) achieves 0.99 bpc, breaking the 1.0 barrier for the first time on this widely-studied benchmark. The improvements are progressive with depth: 12-layer (1.06) → 18-layer (1.03) → 24-layer (0.99), suggesting that deeper models benefit from the increased dependency length afforded by the recurrence mechanism (each additional layer adds roughly one segment length to the maximum dependency).

The training attention length is 784 and evaluation attention length is 3,800 — nearly 5× the training length. The authors note that "Transformer-XL does not need any auxiliary losses" (unlike Al-Rfou et al., 2018, which used auxiliary prediction losses at intermediate layers), attributing all gains to the architectural improvements.

The comparison at matched parameter count is instructive: the 12-layer Transformer-XL (41M, 1.06 bpc) substantially outperforms the 12-layer vanilla Transformer (44M, 1.11 bpc) — a 0.05 bpc improvement from architecture alone. The 64-layer vanilla Transformer's massive depth (64L, 235M) achieves the same 1.06 bpc as the 12-layer Transformer-XL, suggesting that depth in the vanilla model was being used to compensate for the lack of recurrence — deeper layers can indirectly incorporate longer context as representations propagate upward, but inefficiently compared to explicit state reuse.

Character-Level Language Modeling: text8

On text8 (Table 3), the 24-layer Transformer-XL (277M parameters) achieves 1.08 bpc, a new state-of-the-art with a clear margin over the prior best (1.13 bpc from Al-Rfou et al.'s 64L Transformer). The authors use the same model and hyperparameters as enwik8 without further tuning, demonstrating that the architecture does not require dataset-specific optimization. This is a stronger test than it might appear: text8's preprocessing (lowercasing, removing all non-letter characters) makes it a different distribution than enwik8, yet the same architecture transfers effectively.

Word-Level Language Modeling (Short Sequences): One Billion Word

On One Billion Word (Table 4), which lacks long-term dependency due to sentence shuffling, Transformer-XL Large (0.8B parameters) achieves 21.8 PPL, improving the single-model state-of-the-art from 23.7 (Baevski and Auli, 2018, Adaptive Input with 1.0B parameters). The Transformer-XL Base model (0.46B parameters) achieves 23.5 PPL, outperforming the Adaptive Input model with the same parameter count (24.1 PPL). The key comparison is against the contemporary work using vanilla Transformers (Baevski and Auli, 2018) — Transformer-XL substantially outperforms it despite both using Transformer backbones, suggesting that the advantages of the proposed architecture extend beyond long-sequence modeling to general language modeling quality.

The authors attribute this gain primarily to the resolution of the context fragmentation problem (Section 4.2 ablation): even when long-term dependency is not required, starting each segment with a cold start degrades training. The recurrence mechanism provides initial hidden states for each segment, ensuring that even the first token predictions are informed by preceding context.

Word-Level Language Modeling (Small Data): Penn Treebank

On Penn Treebank (Table 5), which has only 1M training tokens, Transformer-XL (24M parameters) achieves 54.52 PPL without finetuning, a new state-of-the-art among single-step training. The best prior result without finetuning was 55.3 (Melis et al., 2018, Dropout tuning with 24M parameters). The results show Transformer-XL also generalizes to small datasets despite being designed primarily for long sequences. The authors apply variational dropout and weight averaging (following AWD-LSTM; Merity et al., 2017), indicating that standard regularization techniques are compatible with the architecture.

The finetuned baselines (AWD-LSTM + Finetune achieves 57.3; MoS + Finetune achieves 54.44) use two-step finetuning procedures that are orthogonal to architecture. Transformer-XL without finetuning matches the best finetuned result, suggesting that finetuning could further improve performance.

Evaluation Speed: Transformer-XL vs. Vanilla Transformer

Table 9 quantifies the evaluation speedup from state reuse at different attention lengths during evaluation on enwik8. Compared to the vanilla Transformer evaluation procedure (which re-processes the full segment from scratch for each new token):

At 3,800 attention length: 1,874× speedup
At 2,800 attention length: 1,409× speedup
At 1,800 attention length: 773× speedup
At 800 attention length: 363× speedup

The speedup increases with attention length because the vanilla model's cost scales linearly with segment length (it reprocesses the entire context for each prediction), while Transformer-XL's cost is effectively constant per token (only the new token is processed; previous states are cached and reused). This is not a model quality result but a pure computational efficiency result — the faster evaluation comes from the architectural design, not from any approximation or quality tradeoff.

Relative Effective Context Length (RECL)

Table 8 reports RECL values with $r = 0.1, 0.5, 1.0$ for multiple architectures:

Transformer-XL 151M: 900 / 800 / 700 (for $r = 0.1, 0.5, 1.0$ respectively)
QRNN: 500 / 400 / 300
LSTM: 400 / 300 / 200
Transformer-XL 128M: 700 / 600 / 500
Transformer-XL with Shaw et al. encoding: 400 / 400 / 300
Transformer-XL without recurrence: 300 / 300 / 300
Vanilla Transformer: 128 / 128 / 128

Transformer-XL's RECL of 900 at $r = 0.1$ means that for the hardest 10% of positions (where short-context models struggle most), increasing the context length continues to provide meaningful gains up to 900 tokens. This is 80% longer than the best recurrent baseline (QRNN at 500) and 450% longer than the vanilla Transformer (which saturates at exactly the segment length of 128 — it cannot use any context beyond the segment boundary). The RECL values decrease as $r$ increases (more positions included) because easier positions require less context, diluting the measured dependency length.

Both components of Transformer-XL contribute independently to RECL: removing recurrence drops RECL from 700 to 300 (at $r = 0.1$ ), and replacing the full relative encoding with Shaw et al.'s version drops RECL from 700 to 400. Using neither component (the vanilla Transformer) collapses RECL to 128 — exactly the training segment length, confirming that the vanilla model cannot exploit any context beyond what it was trained on.

Ablation Studies and Robustness Checks

Comparison of encoding schemes and recurrence on WikiText-103 (Table 6): This is the most comprehensive ablation, testing four encoding schemes (Ours, Shaw et al., 2018, Vaswani et al., 2017 absolute, Al-Rfou et al., 2018 absolute) with and without recurrence, combined with either "Full" loss (cross-entropy on all segment positions) or "Half" loss (cross-entropy only on the most recent half of positions). The results show:

Full Transformer-XL (recurrence + Ours encoding + Full loss): 26.77 PPL best, 500 attention length. This is the best overall result for the 128M parameter configuration.
Shaw et al. encoding with recurrence + Full loss: 27.94 PPL (best and initial identical at 256 attention length — the model does not benefit from extending attention beyond 256). The gap vs. our encoding (27.94 vs. 26.77) demonstrates the value of the global bias terms and the sinusoid inductive bias.
Recurrence without relative encoding (absolute encoding, Half loss): 28.33 PPL best at 460 attention length. Notably, absolute encodings only work with Half loss — with Full loss, performance degrades (29.02 for Ours/Full/no recurrence vs. 28.33 for Ours/Half/no recurrence). The authors explain that "Half loss excludes positions with very short attention lengths during training for better generalization" — positions near the start of a segment have fewer preceding tokens to attend to, so including them in the loss with absolute encodings creates a train-test mismatch when evaluation attention length is extended.
No recurrence, Ours encoding, Full loss: 29.02 PPL best, only 260 attention length. Compared to 26.77 with recurrence, this demonstrates the recurrence mechanism independently improves perplexity by 2.25 PPL and extends effective context from 260 to 500.
No recurrence, absolute encoding (Vaswani et al., 2017 or Al-Rfou et al., 2018), Half loss: 30.97–31.16 PPL with 120 attention length (matching the training segment length). This is the vanilla Transformer baseline — it cannot generalize beyond its training length.

The key interaction: absolute encodings can achieve moderate performance (28.33) when recurrence is present AND Half loss is used, but they cannot generalize to longer evaluation contexts (the best attention length of 460 with this configuration is shorter than with relative encodings). Relative encodings are necessary for full-length generalization.

For the larger 151M parameter configuration (bottom of Table 6), increasing attention length during evaluation from 300 → 450 → 640 progressively improves PPL from 23.43 (at training length, "PPL init") to 23.09 (at 640, "PPL best") — showing that the benefit of longer context is monotonic.

Isolating context fragmentation from long-range dependency on One Billion Word (Table 7): Since One Billion Word has shuffled sentences with no long-range structure, any improvement from recurrence must come from resolving context fragmentation. The results show:

Full Transformer-XL: 25.2 PPL
With Shaw et al. (2018) encodings: 25.7 PPL
Without recurrence: 27.1 PPL

The 1.9 PPL improvement from adding recurrence (27.1 → 25.2) is attributable to fixing context fragmentation alone, since long-range dependency is not a factor. This confirms that context fragmentation is a separable, independently important problem. The 0.5 PPL gap between our encoding and Shaw et al. (25.7 vs. 25.2) shows that the encoding improvements matter even on short sequences — the global bias terms and separated key projections provide benefits beyond length generalization.

Memory-constrained ablation on WikiText-103 (Table 10, Appendix A): To address the concern that the recurrence mechanism uses additional GPU memory (storing cached hidden states), the authors compare Transformer-XL against baselines under the same memory budget. Transformer-XL is given a shorter backpropagation length (128) to compensate for the memory used by the cache, while the baseline without recurrence gets a longer backpropagation length (172–176). Despite the shorter training context, Transformer-XL still outperforms the baseline:

Transformer-XL (backprop 128, recurrence, Ours encoding, Full loss): 26.77 PPL best
Baseline (backprop 176, no recurrence, Ours encoding, Full loss): 27.98 PPL best

This is a strong result: even when forced to use a shorter segment during training (128 vs. 176) to equalize memory, Transformer-XL's recurrence mechanism more than compensates, achieving better perplexity and much longer evaluation attention length (500 vs. 400). This addresses a potential criticism that Transformer-XL's gains come from simply using more memory rather than better architecture.

Component-wise contribution to RECL (Table 8, bottom rows): The RECL ablation isolates the contribution of each component to long-range dependency learning:

Transformer-XL 128M: 700 RECL (r=0.1)
With Shaw et al. encoding: 400 RECL — losing 300 tokens of effective context compared to the full encoding
Without recurrence: 300 RECL — losing another 100 tokens
Vanilla Transformer: 128 RECL — exactly the segment length, confirming zero generalization

The encoding formulation contributes more to RECL than the recurrence mechanism alone (Shaw encoding drops RECL from 700 to 400, while removing recurrence drops it from 700 to 300), but both are necessary to substantially exceed the segment length. The vanilla Transformer's RECL of exactly 128 confirms that fixed-length training without recurrence creates a hard ceiling on dependency length.

Generating coherent long text (Tables 11–13, Appendix E): While not a formal ablation, the paper includes three generated text samples of 500–1,000 tokens from the best WikiText-103 model, noting they were "randomly generated without any cherry picking." The generated text demonstrates: maintenance of Wikipedia section structure, topic coherence over thousands of tokens, chronological ordering (in the Clayton Kershaw example, tracking seasons 2011 → 2012 → 2013), and long-range references (e.g., "another back injury" referring to a previously mentioned injury). These qualitative results support the quantitative claim that Transformer-XL models long-range dependencies, but they are anecdotal — no systematic evaluation of generation quality (e.g., human evaluation, entity coherence metrics) is provided.

Attention visualization (Appendix D, Figures 5–7): The paper provides attention visualizations but does not draw quantitative conclusions. Figure 5 shows the average attention distribution over 640 memory positions for all 160 heads (16 layers × 10 heads). The overall trend is a focus on nearby tokens. However, specific heads exhibit wide attention distributions: head 8 in layer 1 shows near-uniform attention across the entire memory span (screening for higher layers), head 78 in layer 8 shows sparse attention scattered across all ranges, and head 158 in layer 16 shows position-specific sparse attention. The decomposition of attention scores into terms (a), (b), and (d) (Figure 7) shows that term (b) — content-dependent positional bias — largely drives the overall trend of nearby focus, while term (d) — global positional bias — provides a flatter bias toward longer context. These visualizations are consistent with the intended design but do not prove causation.

Critical Assessment

Does the evidence support the claim that Transformer-XL learns dependencies 80% longer than RNNs and 450% longer than vanilla Transformers?

This is the paper's most prominent quantitative claim, and it is supported by the RECL metrics in Table 8, but with important caveats about what RECL actually measures.

What the experiments demonstrate: RECL shows that Transformer-XL continues to benefit from additional context up to ~900 tokens (for the hardest 10% of positions), while LSTM/QRNN saturate at ~400–500 and vanilla Transformers saturate at exactly 128 (the training segment length). The "80%" and "450%" figures are derived from these RECL ratios: 900 vs. 500 (QRNN) = 1.8× or "80% longer," and 700 vs. 128 (vanilla Transformer) = 5.47× or "roughly 450% longer." The ablation in Table 8 shows both components (recurrence and encoding) contribute.

What the experiments do not demonstrate: RECL measures the position on the test set beyond which additional context stops helping, but it is a correlational metric, not a direct measurement of whether specific long-range dependencies are being learned. A model could have a high RECL by extracting diffuse statistical information from long context (e.g., topic-level features, word co-occurrence patterns) without actually resolving specific syntactic dependencies (e.g., correctly linking a pronoun at position 500 to its antecedent at position 100). The paper does not include any targeted evaluation of specific long-range linguistic phenomena — no coreference resolution probes, no subject-verb agreement tests across long distances, no targeted syntactic evaluations. The RECL metric, while well-motivated, is a perplexity-based proxy that does not distinguish between these types of learning.

Additionally, the RECL comparison group in Table 8 uses three models (Transformer-XL, QRNN, LSTM) with similar but not identical parameter counts, and the paper does not report whether all models are trained equivalently (same optimizer, same training data, same computational budget). Differences in training could contribute to RECL differences independently of architecture.

A missing experiment: A synthetic dataset with controlled dependency lengths — for example, sequences where predicting token $t$ requires information from exactly $k$ positions back, with $k$ varying from 10 to 1,000 — would directly test whether Transformer-XL can exploit context at specific distances. The paper's evaluation on natural text, while ecologically valid, conflates multiple factors (topic coherence, local syntax, long-range coreference) that cannot be disentangled.

Does the evidence support the claim that Transformer-XL achieves better performance on both short and long sequences?

This claim is well-supported by the benchmark results. On long sequences:

WikiText-103 (average article length 3.6K tokens): 18.3 PPL, state-of-the-art. The improvement is substantial (10.7% relative over prior best). Table 6 shows that performance continues to improve as evaluation attention length is extended to 640 (well beyond the training length of 128).
enwik8 (100M characters, long document structure): 0.99 bpc, first model to break 1.0. The 12-layer Transformer-XL matches a 64-layer vanilla Transformer with 17% of the parameters.

On short sequences:

One Billion Word (shuffled sentences): 21.8 PPL, state-of-the-art, outperforming contemporary Transformer-based work. Table 7's ablation confirms that recurrence helps even when long-range dependency is impossible, attributable to context fragmentation resolution.
Penn Treebank (1M tokens): 54.52 PPL, state-of-the-art (without finetuning). This is a small dataset where long-range modeling is not the primary challenge.

A caveat on "better performance": The improvements on short-sequence datasets (One Billion Word, Penn Treebank) are meaningful (1.9 PPL on One Billion Word, ~1 PPL on Penn Treebank) but relatively smaller in percentage terms than the long-sequence improvements. The architecture's primary value is clearly on long contexts; the short-sequence benefits are a welcome bonus but not the main story. The paper could be clearer about this asymmetry.

A missing comparison: The paper compares Transformer-XL to prior published results but does not train a vanilla Transformer baseline at the same parameter counts on One Billion Word or Penn Treebank with identical optimization settings. This means the short-sequence improvements could partially reflect training recipe differences (optimizer, learning rate schedule, regularization) rather than pure architectural advantages.

Does the evidence support the claim of up to 1,800× faster evaluation?

This is the most straightforward claim and is directly supported by Table 9: at 3,800 attention length on enwik8, Transformer-XL is 1,874× faster than the vanilla Transformer evaluation procedure. The measurement methodology is clear (per-token time on one GPU).

A nuance the paper does not emphasize: The comparison is specifically against the sliding-window evaluation procedure described in Section 3.1 and Figure 1b, where the vanilla model reprocesses the full segment from scratch for each new token. This is the worst-case baseline — it is how the Al-Rfou et al. (2018) model was evaluated, so the comparison is fair in context, but it means the speedup is relative to a deliberately inefficient algorithm. A vanilla Transformer could be evaluated more efficiently by caching intermediate representations at some computational cost (though this would require architectural modifications). The 1,800× figure should be understood as "1,800× faster than the standard evaluation procedure for fixed-length Transformers," not "1,800× faster than any possible Transformer evaluation."

What would strengthen the claim: Reporting absolute throughput (tokens/second) rather than just relative speedup would help practitioners assess practical deployability. A comparison against a production-optimized LSTM language model would contextualize the speedup.

Does the evidence support the claim that Transformer-XL resolves the context fragmentation problem?

The One Billion Word ablation (Table 7) provides the cleanest evidence: on a dataset with no long-range structure, adding recurrence improves perplexity by 1.9 PPL (27.1 → 25.2). Since long-range dependency cannot explain this gain, it must come from providing better context for the first tokens in each segment.

The strength of this evidence: The experimental design is elegant — the shuffled-sentence property of One Billion Word provides a natural controlled experiment. The result is clean and the interpretation is persuasive.

A weakness: The paper does not directly measure context fragmentation — it infers the resolution of context fragmentation from the perplexity improvement. A direct measurement would track the perplexity of the first $k$ tokens in each segment with and without recurrence. If context fragmentation is the cause, the largest improvements should be concentrated in those first few positions. The paper does not report this analysis, making the causal chain (recurrence → better initial-token context → lower perplexity) an inference rather than a demonstrated mechanism.

Does the evidence support the claim that the relative positional encoding enables length generalization?

Yes, this is one of the strongest pieces of evidence in the paper. Table 6 shows that with the proposed encoding (Ours), evaluation attention length can be extended to 500 (from a training length of 128) on WikiText-103 and to 3,800 (from 784) on enwik8, with perplexity continuing to improve monotonically. With Shaw et al.'s relative encoding, the evaluation attention length cannot be extended meaningfully beyond training (256 max, and performance doesn't improve at that length). With absolute encodings, generalization is even worse.

The ablation in Table 6 also reveals a subtle interaction: absolute encodings require "Half loss" (training only on recent positions) to achieve reasonable performance, because including early positions in the loss creates a mismatch when evaluation context is extended. This empirical finding is consistent with the theoretical argument that absolute encodings create an artificial dependence on position identity that does not generalize.

The strength: The monotonic improvement in perplexity as evaluation attention length increases (Table 6, 151M: 23.43 at 300 → 23.16 at 450 → 23.09 at 640) is direct evidence of generalization. The model was never trained with attention lengths beyond 128, yet it effectively uses context at 640 — the sinusoid inductive bias is working as intended.

A limitation: The paper only tests generalization up to approximately 5× the training length (784 → 3,800 on enwik8; 128 → 640 on WikiText-103). Whether the sinusoid encoding would continue to generalize to 10×, 50×, or 100× the training length is not tested. There is likely a limit at some point — the sin/cos functions have finite frequency resolution — but the paper does not explore where that limit lies.

What are the genuine weaknesses in the experimental design?

Single training paradigm across all datasets: While the paper evaluates on five benchmarks, all experiments use the same basic setup (Transformer-XL trained from scratch on the target dataset's training set). There is no evaluation of Transformer-XL as a pretrained model for downstream tasks (the paradigm that was emerging at the time with BERT, GPT, etc.). This matters because the paper's long-range dependency capabilities would be most valuable in settings where pretrained representations are used for tasks requiring document-level understanding — summarization, question answering, coreference resolution. The paper only demonstrates improved language modeling perplexity, which is a proxy for representation quality but not a direct measurement of downstream usefulness.

No comparison to contemporary sparse attention methods: At the time of this paper, other approaches to extending Transformer context were being developed, including sparse attention patterns (Child et al., 2019, Sparse Transformer) and compressive memory (Rae et al., 2019, Compressive Transformer, published shortly after). The paper does not compare to these because they were largely concurrent, but from a modern perspective, the lack of comparison to any method that also addresses long context (besides the vanilla Transformer) limits the ability to assess Transformer-XL's relative merits.

The generated text examples are anecdotal: Appendix E presents three generated samples as evidence of long-range coherence, noting they are "randomly generated without any cherry picking." While the samples are impressive, no systematic evaluation of generation quality is provided — no human evaluation, no automated metrics, no comparison to baselines. This is qualitative evidence at best, and the paper does not claim otherwise in the main text, but it is worth noting that the "generates reasonably coherent, novel text articles with thousands of tokens" claim in the abstract rests entirely on these three examples.

RECL is a new metric introduced in this paper and validated only on these models: While RECL is well-motivated and improves on prior metrics, it has not been independently validated or adopted by the community. The 1% threshold and the $r$ parameter are arbitrary choices. The paper does not perform a sensitivity analysis to show that RECL rankings are robust to these choices.

The parameter counts are not always matched in comparisons: In Table 8 (RECL), Transformer-XL 151M is compared against QRNN and LSTM whose exact parameter counts are not given — the paper only says they are in the same "model group." Without exact matching, some of the RECL difference could be due to model capacity rather than architecture.

No error bars or statistical significance testing: The paper reports single-number results for perplexity and RECL without confidence intervals. Given that some improvements are modest (e.g., the 18.3 vs. 20.5 gap on WikiText-103 could be within test-set variance for a 103M-token training set), the lack of statistical rigor makes it difficult to assess whether smaller improvements are reliable or within noise.

6. Limitations and Trade-offs

The Recurrence Mechanism Breaks the Standard Transformer Training Paradigm Without Quantifying the Memory-Vs-Compute Tradeoff

The assumption or constraint. The segment-level recurrence mechanism caches hidden states from previous segments and concatenates them to the current segment's context for computing keys and values. This fundamentally changes the memory footprint of training: for each layer, a tensor of shape M × d (memory length × hidden dimension) must be stored alongside the current segment's activations. The paper acknowledges this implicitly in Appendix A (Table 10), where it equalizes GPU memory between Transformer-XL and baselines by giving Transformer-XL a shorter backpropagation length (128 vs. 172–176) — explicitly trading off training context length for memory used by the cache.

The consequence. A practitioner deciding whether to adopt Transformer-XL over a vanilla Transformer needs to understand the real cost per training step, not just the quality improvement. The headline perplexity numbers in Tables 1–5 use a training segment length that is equal to the baseline's segment length, which means Transformer-XL uses strictly more GPU memory during training (it stores both the current segment's activations for backpropagation AND the cached previous-segment states). The paper does not report absolute memory consumption, peak GPU utilization, or the memory-to-quality Pareto frontier. Without this information, it is impossible to determine whether Transformer-XL's perplexity improvements are "real" in a resource-matched sense — a vanilla Transformer given the same GPU memory budget could potentially increase its own segment length and narrow or close the gap.

Table 10 provides the only memory-equalized comparison, showing Transformer-XL maintains an advantage even with shorter backprop, but this is a single data point at one model scale on one dataset. The tradeoff — shorter training context vs. memory cache — may interact differently with model size, sequence length, and batch size in ways the paper does not explore. For large-scale training where GPU memory is the binding constraint, the optimal configuration may favor a longer-segment vanilla Transformer over a shorter-segment Transformer-XL, but the paper provides no guidance on where that crossover point lies.

What evidence exists in the paper. Table 10 (Appendix A) acknowledges the tradeoff and demonstrates one equalized comparison, but reports only perplexity — not memory usage, training time per step, or maximum batch size. The main results tables (1–5) do not report the memory cost of the recurrence mechanism. The paper mentions in Section 3.2 that "we can cache as many previous segments as the GPU memory allows," explicitly tying memory length to hardware constraints, but never quantifies the relationship.

Mitigation status. The paper acknowledges the issue in passing (Appendix A: "Transformer-XL still outperforms the baseline even with a shorter backprop length") but does not provide a systematic study of the memory-quality tradeoff. There is no guidance on how to choose the training segment length vs. memory length given a fixed memory budget, no reporting of absolute memory consumption, and no recommendation for practitioners operating under hardware constraints. This is a consequential gap because memory limitations are often the binding constraint in production training pipelines.

The Relative Positional Encoding's Length Generalization Has No Characterized Upper Bound

The assumption or constraint. A central claim of the paper is that the sinusoid-based relative positional encoding R enables the model to generalize to evaluation attention lengths far beyond those seen during training — from 384 to 1,600 on WikiText-103, from 784 to 3,800 on enwik8. This generalization depends on the mathematical property that R_{i+k} can be expressed as a linear function of R_i, which provides a smooth inductive bias for extrapolating to unseen distances. However, the paper never characterizes where this extrapolation breaks down. The sinusoid encoding uses sine and cosine functions of different frequencies; at very large distances, the highest-frequency components will have cycled many times and the encoding may become indistinguishable from encodings at shorter distances, or the model's learned projections W_{k,R} may not have been trained to handle the extrapolated range.

The consequence. A practitioner training Transformer-XL on segments of length L and deploying it with evaluation memory M ≫ L has no way to predict whether the model will actually benefit from the extended context, or at what point performance will plateau or degrade. The paper shows that performance improves monotonically up to 5× the training length (784 → 3,800 on enwik8; 128 → 640 on WikiText-103), but does not test further extension. If a downstream application requires modeling dependencies over 10,000 tokens (e.g., book-length text, long documents, multi-turn conversations), the paper provides no evidence that Transformer-XL can do so, and the sinusoid encoding's frequency resolution at those distances is untested. The failure mode would be silent: the model would attend based on positional biases that are effectively random for very long distances, degrading rather than improving predictions.

What evidence exists in the paper. The paper demonstrates successful generalization to approximately 5× the training length (Section 4.1: 784 → 3,800 on enwik8; Table 6: 128 → 640 on WikiText-103) but does not test beyond these ratios. The RECL measurements in Table 8 show saturation at approximately 700–900 tokens for Transformer-XL 128M/151M, but these are measured relative to models trained with segment lengths of roughly 128 — the RECL values may reflect the training length ratio rather than an absolute architectural limit. The paper does not include an experiment where training length is varied and maximum usable evaluation length is measured, which would directly characterize the generalization envelope.

Mitigation status. Not addressed. The paper presents the sinusoid encoding's extrapolation property as an unqualified benefit, without discussing any limitations or degradation regimes. There is no suggestion for future work on characterizing or extending the generalization range, and no experiment probing the limit. This is a significant gap because the length-generalization claim is central to the paper's value proposition, yet its bounds are entirely uncharacterized.

The Architecture Is Validated Only on Language Modeling, with No Evidence for Downstream Task Transfer

The assumption or constraint. All experiments in the paper are on the standalone language modeling task — predicting the next token given preceding context, evaluated by perplexity or bits-per-character on held-out text. The paper motivates its work partly through unsupervised pretraining (Section 1: "successful applications such as unsupervised pretraining," citing Dai and Le, 2015; Peters et al., 2018; Radford et al., 2018; Devlin et al., 2018), but never evaluates Transformer-XL as a pretrained model for any downstream task — no fine-tuning on text classification, no feature extraction for sequence labeling, no evaluation on question answering, summarization, coreference resolution, or any other task that would benefit from long-range context.

The consequence. Language modeling perplexity is a proxy for representation quality, not a direct measurement of it. A model could achieve substantially better perplexity by learning to exploit spurious statistical patterns in the training data (e.g., better local n-gram modeling, topic-level features) that do not translate to better representations for tasks requiring genuine semantic understanding. The paper's core claim — that Transformer-XL learns longer-range dependencies — would be most convincingly demonstrated on tasks that require long-range reasoning. If the model cannot outperform baselines on coreference resolution (linking pronouns to antecedents across paragraph boundaries), document-level sentiment analysis, or long-form question answering, then the measured RECL improvements may reflect better statistical modeling of surface patterns rather than deeper linguistic understanding.

This is particularly consequential given the historical context: in 2019, pretrained language models (BERT, GPT, ELMo) were driving practical NLP progress. A practitioner choosing a pretrained backbone for downstream tasks would want evidence that Transformer-XL's architectural advantages transfer — not just that it achieves better perplexity on held-out text. The gap between "better language model" and "better representations for downstream tasks" was well-documented by this point (e.g., perplexity and downstream performance do not always correlate), so the omission is notable.

What evidence exists in the paper. None. The paper evaluates exclusively on language modeling perplexity/bpc across five datasets (WikiText-103, enwik8, text8, One Billion Word, Penn Treebank) — all next-token prediction tasks. The generated text samples in Appendix E are qualitative demonstrations of long-range coherence, but are not a systematic evaluation. There is no fine-tuning experiment, no linear probing, no zero-shot or few-shot evaluation on any task beyond language modeling. The conclusion mentions "unsupervised feature learning" as an envisioned application but provides no evidence.

Mitigation status. Not addressed. The paper acknowledges downstream applications only aspirationally in the conclusion ("We envision interesting applications of Transformer-XL in the fields of text generation, unsupervised feature learning, image and speech modeling") without providing any experimental substantiation. There is no suggestion that this limitation is important to address or that future work should evaluate transfer learning. Given the paper's stated motivation (unsupervised pretraining), this omission substantially weakens the practical case for adoption.

The Evaluation Speedup Comparison Is Against a Straw-Man Baseline That No Production System Would Use

The assumption or constraint. The headline speedup figure of up to 1,874× (Table 9) compares Transformer-XL's evaluation procedure (which caches and reuses hidden states from previous segments) against the vanilla Transformer's sliding-window evaluation with full recomputation — a procedure where each new token prediction requires processing an entire L-length segment from scratch, shifting the window by one position each step. This is indeed how Al-Rfou et al. (2018) performed evaluation, so the comparison is fair within the paper's framing. However, the sliding-window-with-full-recompute procedure is pathologically inefficient in a way that no production deployment would tolerate. A vanilla Transformer can be evaluated more efficiently by caching intermediate values within the current segment (e.g., reusing already-computed key-value pairs for the overlapping portion when the window slides), even without the architectural recurrence mechanism of Transformer-XL. The paper does not compare against this more reasonable baseline.

The consequence. The 1,874× figure, while technically correct for the specific baseline chosen, is misleading as a practical claim about deployment speed. A practitioner comparing Transformer-XL against a reasonably optimized vanilla Transformer inference implementation might see speedups that are much smaller — perhaps 2–10× rather than 1,800×. The paper does not provide the information needed to estimate what the speedup would be in a realistic deployment scenario, making it impossible to do a cost-benefit analysis. The speedup is also measured only on enwik8 (character-level), which has very short segments (784 training, 3,800 evaluation). Word-level models with different context lengths would see different speedup ratios, but the paper does not report evaluation speed for WikiText-103 or other benchmarks.

Additionally, the paper does not compare Transformer-XL's evaluation speed against optimized LSTM language models, which were the production standard at the time. Without this comparison, it is unclear whether Transformer-XL makes Transformer-based language models competitive with LSTMs for low-latency inference or merely less catastrophically slow than the naive vanilla Transformer.

What evidence exists in the paper. Table 9 reports speedup at four attention lengths on enwik8 only. There is no evaluation speed comparison for word-level datasets, no comparison against LSTM baselines, and no absolute throughput numbers (tokens/second). The paper describes the vanilla evaluation procedure in Section 3.1 and Figure 1b, making clear what the baseline does, but does not acknowledge that more efficient caching schemes could reduce the gap.

Mitigation status. Not addressed. The paper presents the speedup numbers without qualification and does not discuss alternative vanilla Transformer evaluation strategies. There is no acknowledgment that the baseline represents a worst-case rather than a realistic deployment scenario, and no suggestion that further engineering of the baseline could reduce the speedup advantage. The absolute throughput (tokens/second) of Transformer-XL is never reported, so a practitioner cannot assess whether it meets latency requirements for their application regardless of the speedup ratio.

The RECL Metric Introduces a New Evaluation Protocol Without Sufficient Validation or Sensitivity Analysis

The assumption or constraint. The paper introduces Relative Effective Context Length (RECL) as a new metric for measuring long-range dependency learning, and uses it as the primary evidence for the claim that Transformer-XL learns dependencies "80% longer than RNNs and 450% longer than vanilla Transformers" (abstract, Section 4.3). RECL depends on several design choices: (1) the 1% relative gain threshold for determining when additional context stops helping, (2) the use of the minimum loss across a model group at a short context length as the calibration baseline, (3) the r parameter that selects the top-r hardest positions, and (4) the step size Δ for incrementing the context length. The paper does not report sensitivity to any of these choices.

The consequence. Without sensitivity analysis, a reader cannot assess whether the RECL rankings are robust or an artifact of the specific threshold and r values chosen. If a model's RECL is 900 at threshold 1% but 300 at threshold 0.5%, then the "80% longer than RNNs" claim depends on the arbitrary choice of 1%. The paper reports RECL for three values of r (0.1, 0.5, 1.0) but not for multiple thresholds or multiple step sizes. Additionally, RECL is defined relative to a model group — the models in each group must be chosen by the experimenter, and different groupings could produce different RECL values. The paper does not justify why particular models are grouped together (e.g., why Transformer-XL 151M is compared against QRNN and LSTM, but not against other architectures in the literature).

More fundamentally, RECL is proposed and used in this paper alone — it has not been validated through independent replication, correlation with downstream task performance, or comparison against alternative long-range dependency metrics. A practitioner evaluating whether Transformer-XL's RECL advantage will translate to their use case has no external evidence to rely on.

What evidence exists in the paper. Table 8 reports RECL for three r values and shows that the relative rankings are preserved (Transformer-XL > QRNN > LSTM > vanilla Transformer at all r values), which provides some evidence of robustness to r. However, the absolute RECL values change substantially with r (Transformer-XL 151M goes from 900 at r=0.1 to 700 at r=1.0), meaning the "80% longer than RNNs" claim varies with the choice of r. The paper does not discuss why 1% was chosen as the threshold, does not vary it, and does not vary the step size. Figure 3 in Appendix C visualizes the unnormalized relative perplexity gains for various context length pairs, providing some qualitative support, but does not directly test RECL's sensitivity.

Mitigation status. The paper acknowledges that its RECL metric differs from and improves upon the prior ECL metric (Khandelwal et al., 2018), providing detailed mathematical justification in Appendix C. However, it does not validate RECL against external criteria, does not perform sensitivity analysis on threshold or step size, and does not discuss limitations of the metric. The metric is treated as an established evaluation protocol rather than a proposed one that requires vetting. Given that the "80%" and "450%" headline claims depend entirely on RECL, the absence of validation is a significant methodological gap.

Hard Problems (Bin 5 Equivalent) in Language Modeling: The Vanishing Benefit of Longer Context on Extremely Difficult Token Predictions

The assumption or constraint. Transformer-XL provides longer effective context for all positions, but the benefit of additional context is not uniform — it depends on whether the extra context actually contains useful signal for the prediction. The RECL metric partially addresses this by focusing on the r-hardest positions (where short context performs worst) when r = 0.1, showing that Transformer-XL benefits these positions most. However, the paper does not characterize the subset of predictions for which even very long context provides no benefit at all — positions where the relevant information is simply not present in the preceding text regardless of how far back the model can look, or where the model fundamentally lacks the capability to make the prediction even with perfect context.

The consequence. The RECL metric measures the point where marginal gains from additional context drop below 1%, but this is an average. Some token predictions may see zero improvement from any amount of additional context (e.g., the first mention of a novel entity, a rare word with no contextual clues, or a prediction requiring world knowledge not present in the text). For these tokens, Transformer-XL's extended context provides no benefit, and the additional computation of processing long memory is wasted. A practitioner deploying Transformer-XL for applications where a substantial fraction of predictions fall into this "unpredictable from context" category (e.g., technical text with many novel terms, code generation, tasks requiring external knowledge) would see diminishing returns from extended context. The paper provides no way to estimate what fraction of tokens fall into this regime for a given domain, and no guidance on when the cost of longer memory outweighs its benefit.

This is analogous to the "hardest problems" limitation in compute-optimal inference-time scaling (where bin 5 problems see near-zero improvement regardless of strategy), though the paper does not frame it in this way. The concept is the same: extending the context window helps only when the necessary information exists in the preceding text and the model has the capacity to use it. When those conditions are not met, the architectural advantages of Transformer-XL are irrelevant.

What evidence exists in the paper. Table 8 shows that RECL decreases as r increases (more positions included), from 900 at r=0.1 to 700 at r=1.0 for Transformer-XL 151M. This confirms that easier positions require less context, but does not directly address positions where even infinite context would not help. The paper does not analyze per-position perplexity as a function of context length for different position types (e.g., function words vs. content words, first mention vs. subsequent mention, in-vocabulary vs. out-of-vocabulary). Figure 4 in Appendix C shows aggregate perplexity decreasing with context length but does not decompose by token type.

The attention visualizations in Appendix D (Figures 5–7) show that some heads attend broadly across memory while others focus narrowly, suggesting heterogeneous context usage, but this is not linked to prediction difficulty or token properties.

Mitigation status. Not addressed. The paper presents longer context as universally beneficial and does not discuss the conditions under which it provides no gain. There is no analysis of prediction difficulty as a function of token properties, no characterization of the "unpredictable tail," and no guidance on when to limit context length for efficiency. Given that practical deployments must make engineering tradeoffs between context length and throughput, this is a significant omission.

7. Implications and Future Directions

How This Work Changes the Landscape

Transformer-XL fundamentally reframes the conversation around Transformer architectures and sequence length from a hardware-constrained implementation detail to an architectural design problem with a principled solution. Before this paper, the prevailing assumption was that Transformers traded recurrence for parallelizability — you got fast training within a fixed window but paid the price of that window being immovable. The possibility of having both recurrence (for unbounded context) and parallel training (for efficiency) wasn't just unexplored; it was implicitly assumed to be contradictory. Transformer-XL demonstrates that this tradeoff is false: recurrence can be introduced at the segment level, between training steps rather than within them, preserving the parallel computation that makes Transformers attractive while enabling information flow across arbitrarily many segments.

The magnitude of this shift sits between a reframing and a new diagnostic. It is not a paradigm shift on the scale of "attention replaces recurrence" — Transformer-XL augments the Transformer rather than replacing it, and the core self-attention mechanism remains unchanged. But it introduces a new axis of architecture design: how to manage state across segment boundaries. Before Transformer-XL, the only design choices for handling long sequences in Transformers were (a) use longer segments (paying quadratic cost in self-attention), (b) use sparse attention patterns, or (c) accept the fixed-length ceiling. Transformer-XL adds a fourth option: (d) carry forward compressed representations from previous segments as an extended memory. This option is qualitatively different from sparse attention because it carries layer-wise representations rather than raw token embeddings, and from longer segments because the memory cost grows linearly rather than quadratically with context length.

The paper also resolves a latent contradiction in the literature. Prior work had shown that Transformers could outperform LSTMs on language modeling (Al-Rfou et al., 2018) despite having a fixed context window, which raised the question: if fixed-length Transformers already beat RNNs, is longer context actually necessary? Transformer-XL answers this by demonstrating that the fixed-length Transformer was winning despite its context limitation, not because fixed context was sufficient. By removing the limitation, Transformer-XL achieves gains that are substantially larger than the gap between the vanilla Transformer and LSTMs — the 12-layer Transformer-XL matches a 64-layer vanilla Transformer with 17% of the parameters (Table 2), and improves WikiText-103 perplexity from 20.5 to 18.3 (Table 1). This implies that the Transformer architecture's true potential was being masked by the training procedure, and that context management is a first-order factor in model quality, not a secondary concern.

The paper makes certain research directions dramatically more attractive:

Segment-level recurrence as a plug-in component. The recurrence mechanism is architecturally clean — it requires no changes to the core Transformer layer, only to how inputs are prepared and how states are cached between segments. This makes it retrofittable onto any existing Transformer codebase with minimal modifications. The strong results across five benchmarks (word-level and character-level, large and small datasets, long-range and short-range tasks) suggest the gains are robust and not dataset-specific, encouraging adoption as a standard component rather than a niche technique for long-document tasks.
Positional encoding as a first-class design space. By demonstrating that the choice of positional encoding is existentially tied to the ability to reuse hidden states, the paper elevates positional encoding from an implementation detail to a central architectural concern. Prior work had explored relative encodings as a performance improvement (Shaw et al., 2018); Transformer-XL shows they are enabling technology for any architecture that carries state across segments. This opens the door to further innovation in positional encoding — learnable relative encodings with better inductive biases, multi-scale positional representations, or task-adaptive position encoding — not as marginal tweaks but as critical enablers of new capabilities.
Context fragmentation as a diagnosable and solvable problem. By naming and isolating context fragmentation (the degradation of predictions at segment boundaries due to missing preceding context), the paper gives the field a concrete diagnostic. Future architectures can be evaluated not just on aggregate perplexity but on whether they reduce the performance gap between boundary and interior token predictions. The One Billion Word ablation (Table 7) provides a template for isolating fragmentation from long-range dependency: test on a dataset where long-range structure is absent, and any improvement from recurrence can be attributed to fragmentation resolution.

Conversely, some research directions become less urgent:

Building ever-deeper vanilla Transformers to compensate for limited context. Al-Rfou et al. (2018) showed that a 64-layer Transformer could match what Transformer-XL achieves with 12 layers, suggesting depth was being used as an inefficient proxy for recurrence — each additional layer propagates information one step further, but at quadratic cost per layer rather than linear cost through memory. Transformer-XL's results make this approach look like a dead end: depth helps, but it's far less efficient than explicit state reuse.
Auxiliary losses for long-range dependency. Al-Rfou et al. (2018) used auxiliary prediction losses at intermediate layers to encourage the model to use longer context. Transformer-XL achieves better results without any auxiliary losses, suggesting the problem was architectural (no path for information to flow) rather than optimization-related (insufficient training signal). Auxiliary losses may still have value, but they are not a substitute for giving the model a mechanism to access distant context.

Follow-Up Research This Work Enables

Quantifying the precise tradeoff between training segment length, memory length, and GPU memory consumption. The paper acknowledges (Appendix A, Table 10) that the recurrence mechanism consumes additional GPU memory and compensates by reducing training segment length, but provides only a single data point. A systematic study would train Transformer-XL at fixed total GPU memory across a grid of (segment length, memory length) pairs on WikiText-103, measuring both perplexity and wall-clock training time. The output would be a Pareto frontier showing the optimal allocation of memory between current-segment activations and cached previous-segment states, answering the practical question: given a GPU with 16GB/32GB/80GB, what (segment length, memory length) combination maximizes perplexity per training hour? This is essential for practitioners making hardware allocation decisions and would test whether the heuristic of setting memory equal to segment length during training (used in the paper) is actually optimal, or whether asymmetric allocations (e.g., short segment + long memory, or long segment + short memory) perform better at different model scales.

Probing whether Transformer-XL learns genuine syntactic dependencies at long range, or only diffuse statistical features. The RECL metric (Table 8) shows the model continues to benefit from additional context up to 900 tokens, but RECL is a perplexity-based proxy that cannot distinguish between learning that a specific pronoun refers to a specific antecedent at distance 500, versus learning that the overall topic has shifted and adjusting the unigram distribution accordingly. A targeted evaluation would construct a synthetic dataset where token t can only be predicted correctly by attending to a token at exactly position t-k (with k ranging from 10 to 1,000), and where all intervening tokens are uninformative. Measuring accuracy as a function of k for Transformer-XL vs. an LSTM baseline vs. a vanilla Transformer would reveal the shape of each model's dependency learning — not just the maximum distance, but whether the model's ability decays gradually (suggesting genuine long-range attention) or drops off a cliff at the segment boundary (suggesting the RECL gains come from segment-boundary resolution rather than genuine long-range attention). The attention visualizations in Appendix D already show some heads with wide attention spans (head 8 in layer 1, head 78 in layer 8), but the paper does not link these to specific dependency types. This experiment would directly test the paper's central claim.

Transformer-XL as a pretrained encoder for document-level NLP tasks. The paper evaluates only on language modeling perplexity, but the architecture's core value proposition — longer effective context — should be most impactful on tasks requiring cross-sentence or cross-paragraph reasoning. A strong follow-up would pretrain Transformer-XL (and a vanilla Transformer baseline at matched perplexity) on WikiText-103 or a larger corpus, then fine-tune and evaluate on: (a) coreference resolution (e.g., OntoNotes, measuring F1 on pronoun-antecedent pairs separated by various distances), (b) document-level relation extraction (e.g., DocRED), (c) long-form question answering (e.g., NarrativeQA, where questions require synthesizing information across paragraphs), and (d) summarization of long documents (e.g., PubMed, arXiv). The key measurement is the performance gap between Transformer-XL and the baseline as a function of the distance between relevant pieces of information in the input — the paper predicts that Transformer-XL's advantage should grow with distance. A null result (no downstream gain despite better perplexity) would challenge the assumption that language modeling perplexity improvements translate to representation quality, and would force a re-examination of what RECL actually measures.

Stress-testing length generalization beyond 5× the training length to find the breaking point. The paper demonstrates successful generalization from training segment length 128 to evaluation attention length 640 (5×) on WikiText-103, and from 784 to 3,800 (4.8×) on enwik8. But the mathematical property that enables extrapolation — the sinusoid encoding's linear relationship between R_{i+k} and R_i — has limits: at very large distances, the highest-frequency sinusoid components will cycle many times, and the encoding for distance 10,000 may become indistinguishable from distance 10,000 - 2π/ω for some frequency ω. A targeted experiment would train Transformer-XL on segments of length 128 on a synthetic long-range dependency task (to control for other confounds), then measure performance as evaluation memory is increased from 128 to 128,000 in logarithmic steps. The output would be a curve showing where performance plateaus or degrades, characterizing the practical generalization envelope. This would tell practitioners at what document length they need to retrain with longer segments rather than relying on extrapolation. A negative result (early degradation) would motivate research into positional encodings with better extrapolation properties, such as learned Fourier features or adaptive frequency scaling.

Combining segment-level recurrence with sparse or linear attention for even longer context. Transformer-XL's memory mechanism solved the cross-segment information flow problem, but the within-segment self-attention still costs O(L²). For very long segments or very long total context, this becomes the bottleneck. A natural extension would replace the full self-attention within each segment with a sparse or linear-complexity attention variant (e.g., sliding window + global attention as in Longformer, or kernelized attention as in Performer), while retaining the segment-level recurrence for cross-segment propagation. The hypothesis is that the recurrence mechanism and sparse attention serve complementary roles: sparse attention handles local coherence efficiently, recurrence propagates information across arbitrarily distant segments. An experiment would compare (a) Transformer-XL with full attention, (b) Sparse Transformer without recurrence, and (c) Sparse Transformer-XL (sparse attention + recurrence) on WikiText-103 and a long-document benchmark (e.g., PG-19, books). The key question is whether the combination yields multiplicative gains (recurrence helps sparse attention by providing global context that individual sparse patterns miss) or subadditive gains (the recurrence already captures what sparse attention would lose).

Developing and validating a taxonomy of token positions by their dependency distance requirements. The RECL metric shows average behavior, but the per-position benefit of long context likely varies systematically by token type — function words may be predictable from very local context, while content words in later mentions of an entity may require long-range coreference resolution. A detailed analysis would annotate a subset of WikiText-103 test tokens by: (a) part of speech, (b) whether the token is a first mention or subsequent mention of its referent, (c) the distance to the most informative preceding context token (approximated by gradient-based attribution or by measuring perplexity change when context is ablated). Then, measure Transformer-XL's per-token perplexity improvement over the vanilla Transformer for each category. The output would be a "benefit profile" showing which linguistic phenomena actually benefit from longer context, and which see no improvement (indicating either that the information isn't in the text, or that the model cannot use it). This would transform RECL from a single number into a diagnostic tool, and would guide practitioners on which applications to target.

Practical Applications and Downstream Use Cases

Long-document text generation with maintained coherence. The paper demonstrates (Appendix E, Tables 11–13) that Transformer-XL trained on WikiText-103 (only 103M tokens) generates articles of thousands of tokens with maintained topic, chronological ordering, and long-range references (e.g., "another back injury" correctly referencing an earlier injury 500 tokens prior). The practical value is for applications requiring coherent long-form generation — automated report writing, story generation, long-form question answering — where vanilla Transformers with fixed-length contexts frequently lose the thread. The 1,874× evaluation speedup (Table 9) makes this practical for interactive applications: generating a 1,000-token article with attention over 3,800 tokens of context can be done in effectively real time on a single GPU, whereas the vanilla sliding-window approach would be prohibitively slow. The generated text quality is not perfect (the paper acknowledges "minor flaws") but is "relatively coherent" without cherry-picking — sufficient for assisted writing or draft generation where a human editor refines the output.

Cost-efficient batch inference for language model scoring and evaluation. For organizations that run language models over large document collections — e.g., scoring the likelihood of text under a model for filtering, ranking, or anomaly detection — Transformer-XL's amortized O(1) per-token evaluation cost replaces the vanilla Transformer's O(L) per-token cost. On a corpus of 10⁹ tokens with segment length 380, the 1,874× speedup translates directly to a ~1,800× reduction in GPU-hours, turning a computation that would require weeks of GPU time into one that completes in hours. The practical deployment requires only that previously computed hidden states are cached as the model scans through the corpus sequentially — a straightforward engineering change to any existing Transformer inference pipeline. This is a direct cost-saving application that does not require any change to the model's training or output quality; it is purely an inference efficiency improvement.

Pretraining foundation models with extended effective context for downstream transfer. The paper shows that Transformer-XL learns representations that capture information across ~900 tokens of context (RECL, Table 8), compared to 128 for vanilla Transformers. A model pretrained with Transformer-XL on a large corpus (e.g., C4, The Pile) would produce token representations that encode document-level context, which could benefit downstream tasks requiring cross-sentence reasoning — legal document analysis (where clauses reference each other across pages), scientific literature review (where claims in the discussion section depend on methods described earlier), and multi-turn dialogue systems (where responses must be consistent with conversation history). This is not yet demonstrated (the paper evaluates only perplexity), but the architectural properties make it a natural application. The key deployment decision is whether the memory overhead of caching per-layer hidden states during pretraining is justified by the downstream gains; the paper's ablation showing Transformer-XL outperforms baselines under equal memory (Table 10) provides initial evidence that it is.

Deployment of Transformer-based language models in latency-sensitive settings. Before Transformer-XL, using a Transformer language model for autoregressive generation with long context was impractical — each token required processing the full context window, making generation latency proportional to context length. The 1,874× evaluation speedup means that Transformer-XL's per-token latency is effectively constant regardless of how much context is maintained, making it competitive with optimized LSTM implementations for interactive applications. This enables Transformer-based language models in settings where they were previously excluded: mobile keyboard prediction, real-time speech recognition rescoring, and server-side autocomplete with low latency requirements. The absolute throughput (tokens/second) is not reported in the paper, so practitioners would need to benchmark on their own hardware, but the relative speedup over the vanilla evaluation procedure is large enough to cross the threshold from "batch only" to "interactive viable" for many applications.

🎯 Pitch

1. Executive Summary

2. Context and Motivation

The Core Problem: Transformers Have a Fixed-Length Context Ceiling

Pathology 1: The Hard Upper Bound on Dependency Length

Pathology 2: Context Fragmentation

Pathology 3: Cripplingly Slow Evaluation

Why This Problem Matters

Prior Approaches and Where They Fall Short

RNN-Based Language Models and Their Extensions

The Vanilla Transformer LM (Al-Rfou et al., 2018)

Relative Positional Encodings in Prior Work

How This Paper Positions Itself

3. Technical Approach

3.1 Reader Orientation

3.2 Big-Picture Architecture (Diagram in Words)

3.3 Roadmap for the Deep Dive

3.4 Detailed, Sentence-Based Technical Breakdown

Vanilla Transformer Language Model and Its Limitations

Segment-Level Recurrence with State Reuse

Relative Positional Encodings

Complete Forward-Pass Equations

Efficient Computation of the Relative Positional Bias

Design Choices and Their Justifications

4. Key Insights and Innovations

Innovation 1: Recurrence as a First-Class Mechanism in Purely Self-Attentive Models

Innovation 2: Difficulty-Conditioned Strategy Selection as a New Dimension of Model Design

Innovation 2: Relative Positional Encoding as an Enabling Technology Rather Than a Mere Variant

Innovation 3: Context Fragmentation as a Named, Diagnosed, and Resolved Pathology

Innovation 4: The Effective Context Length as an Empirically Validated Measure of Architectural Quality

5. Experimental Analysis

Evaluation Methodology

Main Quantitative Results

Word-Level Language Modeling: WikiText-103

Character-Level Language Modeling: enwik8

Character-Level Language Modeling: text8

Word-Level Language Modeling (Short Sequences): One Billion Word

Word-Level Language Modeling (Small Data): Penn Treebank

Evaluation Speed: Transformer-XL vs. Vanilla Transformer

Relative Effective Context Length (RECL)

Ablation Studies and Robustness Checks

Critical Assessment

Does the evidence support the claim that Transformer-XL learns dependencies 80% longer than RNNs and 450% longer than vanilla Transformers?

Does the evidence support the claim that Transformer-XL achieves better performance on both short and long sequences?

Does the evidence support the claim of up to 1,800× faster evaluation?

Does the evidence support the claim that Transformer-XL resolves the context fragmentation problem?

Does the evidence support the claim that the relative positional encoding enables length generalization?

What are the genuine weaknesses in the experimental design?

6. Limitations and Trade-offs

The Recurrence Mechanism Breaks the Standard Transformer Training Paradigm Without Quantifying the Memory-Vs-Compute Tradeoff

The Relative Positional Encoding's Length Generalization Has No Characterized Upper Bound

The Architecture Is Validated Only on Language Modeling, with No Evidence for Downstream Task Transfer

The Evaluation Speedup Comparison Is Against a Straw-Man Baseline That No Production System Would Use

The RECL Metric Introduces a New Evaluation Protocol Without Sufficient Validation or Sensitivity Analysis

Hard Problems (Bin 5 Equivalent) in Language Modeling: The Vanishing Benefit of Longer Context on Extremely Difficult Token Predictions

7. Implications and Future Directions

How This Work Changes the Landscape

Follow-Up Research This Work Enables

Practical Applications and Downstream Use Cases

Adjacent in domain

Parameter-Efficient Transfer Learning for NLP

A Style-Based Generator Architecture for Generative Adversarial Networks