Transformer-XL & Reformer: Handling Longer Sequences

The original transformer's context problem

Standard self-attention computes a score between every pair of tokens in a sequence, which costs O(n²) in both time and memory. In practice, this forced early transformers into a fixed, fairly short context window — a few hundred to a couple thousand tokens. Anything longer had to be chopped into independent segments, and each segment was processed with no memory of what came before it. That meant a sentence split across a segment boundary lost context, and the model simply couldn't reason over long documents, books, or codebases. Two papers, released within months of each other, attacked this from different angles: Transformer-XL extended effective context through recurrence, and Reformer cut the cost of attention itself.

Transformer-XL: segment-level recurrence

Transformer-XL (2019) borrowed an idea from RNNs: carry a memory from one segment to the next. Instead of processing each fixed-length chunk of text in isolation, Transformer-XL caches the hidden states computed for the previous segment and reuses them as extra context when processing the current segment — without back-propagating gradients through that cached memory, which keeps training tractable.

This gave the model effective context far longer than any single segment, because information could flow across segment boundaries through the cached states, segment after segment, like a conveyor belt of memory. To make this work, Transformer-XL also had to replace absolute positional encodings (which would be ambiguous once segments share positions) with relative positional encodings, which describe how far apart two tokens are rather than their absolute index. Relative position encoding later became standard in many long-context model designs.

Reformer: making attention itself cheaper

Reformer (2020) took a different approach: rather than caching memory across segments, it redesigned attention to scale sub-quadratically with sequence length. Standard self-attention needs every token to compare against every other token. Reformer's insight was that for softmax attention, only a token's nearest neighbors in embedding space actually contribute meaningfully to its output — most attention weight concentrates on a handful of highly relevant tokens, with the rest contributing almost nothing.

Reformer exploits this with locality-sensitive hashing (LSH) attention: it hashes queries and keys into buckets such that similar vectors are likely to land in the same bucket, then only computes attention within each bucket (plus adjacent ones). Instead of comparing every token to every other token, each token only compares against a small, relevant subset — turning O(n²) attention into roughly O(n log n).

Reformer's other trick: reversible layers

LSH attention addresses compute cost, but Reformer also tackled memory cost. Standard transformers must store every layer's activations for use during backpropagation, which becomes prohibitive for very deep models on long sequences. Reformer borrowed reversible residual layers from RevNets: instead of storing activations, each layer is designed so its input can be reconstructed exactly from its output during the backward pass. This lets Reformer train deep models on long sequences using memory that doesn't grow with the number of layers — a huge win for scaling to book-length inputs on limited hardware.

Transformer-XL vs Reformer

What's next

Transformer-XL and Reformer show two complementary strategies for scaling context: smarter memory reuse and smarter attention computation. From here, it's worth stepping back from architecture to look at how language models are evaluated along a different axis entirely — the split between understanding language and generating it, covered next in NLU vs NLG.