Transformer-XL

Introduces a recurrence mechanism at the segment level, where the hidden state sequence computed for the previous segment is cached and reused as an extended context for the current segment.

• Mechanism: During training, the hidden states from the previous segment are frozen and concatenated with the current segment's inputs.
• Information Flow: This creates a recurrent connection that allows gradient and information flow across segments, effectively expanding the receptive field beyond the fixed context window.
• Benefit: Eliminates the context fragmentation problem where a vanilla Transformer cannot model dependencies that span across arbitrary segment boundaries.

Replaces absolute positional encodings with a relative positional encoding scheme that parameterizes the attention score based on the relative distance between query and key tokens.

• Formulation: The attention logit is decomposed into four components: content-based key addressing, content-dependent positional bias, a global content bias, and a global positional bias.
• Key Insight: By encoding only relative distances rather than absolute positions, the model can generalize to sequence lengths never seen during training.
• Reusability: The cached hidden states from previous segments do not carry stale absolute position information, making recurrence coherent.

A dedicated caching mechanism stores the hidden state sequences from previous segments, eliminating redundant computation during both training and inference.

• Training: Hidden states from the previous segment are detached from the computation graph, preventing gradients from flowing across more than one segment boundary and keeping training memory-efficient.
• Inference: The cache enables fast autoregressive decoding by reusing previously computed representations, achieving up to 1,800x speedup compared to recomputing from scratch for each new token.
• Practical Impact: Makes processing of long-form documents like books or extended conversations computationally tractable.

Through the combination of recurrence and relative encoding, Transformer-XL achieves an effective context length that grows linearly with the number of layers and segments.

• Receptive Field: Each layer captures dependencies across N × L tokens, where N is the number of layers and L is the segment length.
• Comparison: A 12-layer Transformer-XL with 512-token segments captures dependencies across 6,144 tokens, while a vanilla Transformer is limited to 512.
• Empirical Result: Achieves state-of-the-art perplexity on long-range language modeling benchmarks like WikiText-103 and enwik8, significantly outperforming vanilla Transformers and LSTM baselines.

The relative positional encoding enables the model to extrapolate to longer segment lengths at evaluation time than those seen during training.

• Capability: A model trained on segments of length 128 can be evaluated on segments of length 256 or 512 without any architectural changes or fine-tuning.
• Mechanism: Because the positional bias depends only on relative distance and not absolute position, the attention mechanism naturally handles longer sequences.
• Practical Value: Provides flexibility to trade off between memory constraints and context length at deployment time without retraining.

Employs shared input and output embeddings with an adaptive softmax to efficiently handle large vocabulary sizes common in character-level and subword-level language modeling.

• Adaptive Softmax: Clusters the vocabulary into capacity tiers, assigning more parameters to frequent tokens and fewer to rare tokens, reducing the computational bottleneck of the final projection layer.
• Weight Tying: Sharing the embedding matrix between input and output layers acts as a form of regularization and reduces the total parameter count.
• Synergy: This combination is particularly effective for datasets with large vocabularies, where a standard softmax would dominate training time.

The core innovation of Transformer-XL that caches and reuses the hidden states from previous context segments during training. Instead of processing each segment independently, the model attends to the cached representations of prior segments, creating a recurrent connection across segments. This mechanism enables the effective context to extend far beyond the fixed segment length, capturing dependencies that span thousands of tokens without the quadratic cost of attending to the entire sequence at once.

• Hidden states from segment n-1 are frozen and fed as extended context for segment n
• Gradients are not propagated through cached states, keeping training efficient
• Enables a theoretically infinite receptive field during inference

Transformer-XL replaces absolute positional encodings with a relative positional encoding scheme that encodes the distance between any two tokens rather than their absolute positions. This is essential for the recurrence mechanism: cached hidden states from previous segments have absolute positions that would conflict with the current segment's positions. By using relative distances, the model generalizes to sequence lengths unseen during training.

• Uses sinusoidal formulation to encode relative distance as a bias added to attention scores
• Decouples positional information from token embeddings
• Enables the model to learn shift-invariant attention patterns

The self-attention computation in Transformer-XL is decomposed into four terms that explicitly model content-based and position-based interactions using relative distances. The attention score between query q_i and key k_j incorporates:

• Content-to-content: q_i · k_j — standard token similarity
• Content-to-position: q_i · R_{i-j} — how query content relates to relative position
• Position-to-content: u · k_j — a global content bias
• Position-to-position: v · R_{i-j} — a global positional bias

Where R_{i-j} is the relative positional encoding and u, v are learnable parameter vectors.

During inference, Transformer-XL maintains a fixed-size memory cache of the hidden states from the most recent segment. When processing a new segment, the model concatenates this cached memory with the current segment's hidden states before computing attention. This avoids recomputing representations for tokens that have already been processed.

• Cache size is a hyperparameter controlling the memory length
• At evaluation time, the cache enables processing sequences 1,800x faster than vanilla Transformers on long documents
• The cache acts as a form of episodic memory for the model during generation

Standard Transformers process text in fixed-length, non-overlapping segments with no information flow between them. This creates a hard boundary at each segment edge, preventing the model from capturing dependencies that cross segment boundaries. The model has zero context of what came before the current segment, which is particularly damaging for tasks requiring long-range coherence like document-level language modeling or multi-paragraph generation.

• Maximum context is strictly bounded by the segment length
• No parameter sharing or state passing between segments
• Leads to context fragmentation and poor performance on long sequences

Transformer-XL achieves dramatic speedups during evaluation compared to vanilla Transformers by reusing cached states. A vanilla Transformer must reprocess the entire preceding context for each new token prediction, leading to quadratic complexity in sequence length. Transformer-XL only processes the current segment while attending to the cached memory, reducing evaluation time from days to hours on benchmarks like WikiText-103.

• Achieves state-of-the-art perplexity on long-range language modeling benchmarks
• Enabled training on the 1-billion-token WikiText-103 dataset with coherent long-range generation
• The recurrence mechanism adds minimal training overhead while delivering massive inference gains