Longformer,
explained.

Rung 1 keeps the window small and remembers across windows. This rung makes the window itself long, by attacking the reason it could not be: comparing every position with every other is quadratic, so doubling the sequence quadruples the cost, and a few thousand tokens is where that becomes unaffordable.

The change is to stop attending to everything. Each token attends only to a sliding window of its neighbours, which makes the cost linear in sequence length rather than quadratic. Information still travels further than the window, because stacking layers composes overlapping windows the way stacked convolutions grow a receptive field, and dilating some windows — attending to every kth neighbour instead of every one — can widen the reach at no extra cost (the paper uses it only in its character-level model).

The piece that makes it work on real tasks rather than just on perplexity is small and important: a handful of global tokens that attend to the whole sequence and are attended by all of it. A classification token or the tokens of a question need to see everything, and a pure window pattern would deny them that. So the pattern is task-aware by design — you choose which positions get global attention based on what the model is for, which is a deliberate departure from the uniformity of rung 2 on the transformer ladder.

Self-attention's power comes from letting every token look at every other token — but that is also its curse. With a sequence of n tokens, there are n² pairs to score, so both compute and memory grow with the square of the length. Double the input and the cost quadruples. This is why the original BERT-style transformers were capped around 512 tokens: a full document of a few thousand tokens would blow past any reasonable memory budget.

But do you really need all-to-all attention? In language, most of what a word depends on is nearby — the phrase it's in, the sentence around it. Long-range links exist, but they are sparse. Longformer's bet is that you can get most of the benefit of full attention with a mostly-local pattern, plus a little global connectivity where it matters — and pay only linear cost.

The core move: instead of attending to all n tokens, each token attends only to a fixed window of w neighbors around it — like a convolution's kernel, but for attention. That changes the arithmetic completely:

The window size w is a fixed constant, so the cost n·w grows only linearly with sequence length — double the document and the cost merely doubles. The saving over full attention is n/w, and it grows with the document: at 4,096 tokens with a 512 window, that is 8× fewer pairs; at 16,384 tokens, 32× fewer. The longer the input, the more the window helps. The runnable version below computes these costs directly.

A fair objection: if a token only sees w neighbors, how can the model capture a dependency spanning the whole document? The same way a convolutional network does — through depth. A token's window covers its neighbors; those neighbors' windows cover their neighbors; so with each stacked layer the receptive field widens. After enough layers, information can flow from any token to any other, even though no single layer looked far.

Longformer also borrows dilation from convolutions: a dilated window has gaps, so it reaches further for the same number of connections — like looking at every other token instead of every adjacent one. In the paper this is used sparingly: only the character-level language model dilates (a small dilation on a couple of heads in upper layers), and the widely used RoBERTa-based Longformer does not dilate at all. Depth alone builds the receptive field there, with the per-layer cost staying linear.

Some tokens genuinely need to see everything, and waiting for depth to route information to them is too slow. So Longformer designates a handful of global tokens: they attend to all tokens, and all tokens attend to them. These are placed where the task needs a global summary — the [CLS] token for classification, the question tokens in question answering.

Because only a few tokens are global, they add just a linear term to the cost. The result is a pattern that is overwhelmingly local and cheap, with a thin backbone of global connectivity for whatever the task needs to see whole — the best of both worlds at linear price.

Longformer, from Beltagy, Peters and Cohan at the Allen Institute for AI, replaces each self-attention layer with a sparse pattern that a pretrained model can adopt without changing anything else. The paper uses it in two settings: a character-level language model trained from scratch, and a RoBERTa model extended to 4,096 tokens and fine-tuned on long-document tasks.

1. Sliding window. Each token attends to w/2 tokens on each side, so a layer costs O(n × w). The pretrained Longformer uses w = 512 in every layer.
2. Dilation, only where it helps. A window with gaps of size d covers d × w positions for the same cost. In the character model the lower layers use no dilation, and the higher layers apply a small dilation on only two heads, so most heads keep fine local detail while a few look further.
3. Windows that grow with depth. In the character model, windows are small in the bottom layers and larger at the top: local patterns first, wider context later.
4. Global attention on chosen tokens. A few positions, chosen per task, attend to every token, and every token attends to them. These are the classification token for classification, the question for question answering, and the question plus the candidate answers for WikiHop.
5. Separate projections for global attention. Global attention gets its own query, key and value projections, initialized from the local ones, so the two kinds of attention can learn different behaviour.
6. A kernel that makes sparsity pay. A masked dense matrix multiply costs as much as full attention, so the paper provides three implementations: a loop, which is memory-efficient but slow; a chunked version that splits the sequence into overlapping blocks of size w and uses ordinary matrix multiplies, without dilation, used for pretraining and fine-tuning; and a custom CUDA kernel written with TVM that supports dilation, used for the character model.
7. Staged training for the character model. Training ran in five phases, starting at sequence length 2,048 with a window of 32, roughly doubling both each phase while halving the learning rate, and ending at 23,040 characters with a window of 512.
8. Continue pretraining from RoBERTa. For downstream tasks the authors start from RoBERTa's weights and set the window to 512. They initialize 4,096 position embeddings by copying RoBERTa's 512 learned ones eight times, then continue masked-language-model pretraining for 65,000 updates at length 4,096 on a mix of books, Wikipedia, and long news and story documents.
9. Fine-tune with global tokens, and LED for generation. Fine-tuning puts global attention on the task tokens. The Longformer-Encoder-Decoder (LED) uses the same pattern in the encoder of a BART-initialized model, for inputs up to 16,384 tokens.

Why copying the position embeddings works

Within any 512-position stretch, the copied embeddings are exactly RoBERTa's, so the local relative structure that attention learned is preserved almost everywhere. Only the seams every 512 positions are new. Training therefore starts close to RoBERTa's quality, instead of relearning position from scratch with a random initialization.

• w — the window size, the number of neighbours each token attends to; 512 in the pretrained model.
• δ — the dilation, the gap between attended positions; 1 means a contiguous window.
• 𝒢 — the global tokens, picked per task. Ordinary tokens add them to their own window.
• s, g — the two projection sets: the local projections used by ordinary tokens, and the separate projections used to compute the global tokens' own outputs.
• ℓ · δ · w — the receptive field at the top of a stack of ℓ such layers.

At the extremes: with w = n every token sees every other and the layer is ordinary full attention, so BERT is a special case. Making every token global also gives back full attention, at full cost. With w small and no global tokens, information needs many layers to cross a document: 12 layers of a 512 window reach about 6,000 tokens. A large δ widens reach but skips neighbours, which is why the paper keeps most heads undilated.

Two kinds of experiment. First, character-level language modeling on text8 and enwik8, to test the attention pattern by itself: a small 12-layer model reached 1.10 bpc on text8 and 1.00 on enwik8, state of the art for models of that size, and a large 30-layer model with 102M parameters reached 0.99 on enwik8, matching larger models. Second, a RoBERTa-based Longformer at 4,096 tokens, fine-tuned and compared with RoBERTa, which has to cut or chunk anything past 512 tokens.

The pattern of gains is the finding. They are largest where documents are long and the answer depends on connecting distant parts, such as Hyperpartisan and WikiHop, and smallest where most inputs already fit in 512 tokens, such as IMDB and OntoNotes. Longformer-large set new state-of-the-art results on WikiHop and TriviaQA, and the encoder-decoder version, LED, did the same for arXiv summarization.

The ablations support the design. On text8, windows that grow from the bottom layer to the top beat both fixed and shrinking windows, and dilation on two heads added a small further gain. On WikiHop, removing the separate global projections hurt, and removing global attention as well hurt much more. In pretraining, copying RoBERTa's position embeddings gave a far better starting loss than random initialization.

The negative result is in the engineering: the saving only appears with the custom chunked or CUDA implementations, because a masked dense multiply costs as much as full attention.

The honest admission is in the engineering rather than the method: realising the theoretical saving requires a custom kernel, because a sparse attention pattern expressed as a masked dense matrix multiply costs exactly what dense attention costs. Sparsity on hardware built for dense arithmetic is not free, and the paper had to write the kernel to get the numbers.

The methodological cost is that no two distant tokens interact directly — any long-range relationship must be composed through depth, which is strictly weaker than one attention operation seeing both ends, and the global tokens are a hand-placed exception to a limitation rather than a removal of it.

How it held up: this is the most instructive reversal on the ladder. The field largely abandoned approximate attention, and the reason is that the diagnosis was wrong about which resource was scarce. Attention's practical bottleneck at these lengths turned out not to be arithmetic but memory traffic — writing an enormous intermediate matrix out to slow memory and reading it back. Once that was fixed by never materialising the matrix, exact attention became fast enough that giving up exactness to save operations stopped paying. Sliding windows did survive, but as one component inside hybrid designs rather than as the answer, and the lesson — profile which resource is actually binding before redesigning the mathematics — is the transferable one.

Longformer was part of a wave of efficient transformers (alongside Reformer, BigBird, and others) all attacking the quadratic-attention bottleneck with different sparsity patterns. Its particular combination — sliding window + global tokens, with dilation in the character model — was clean, effective, and easy to adopt, and it became a go-to for long-document NLP.

The broader arc is worth noting. Sparse-attention patterns like Longformer's were one answer to long context; a different answer arrived later from the systems side — FlashAttention made full attention dramatically cheaper by reorganizing the computation, and hardware kept growing, so many modern models run full attention over long contexts after all. But the question Longformer sharpened — how much attention does a token actually need? — remains central, and sparse patterns are back in force as context windows stretch toward millions of tokens.

Work each one out before you open it — a number, a prediction or a reason, not a definition. Producing the answer is what makes it stick. Your progress is kept on this device.

Attention costs quadratic in sequence length. Six attempts to escape that, ending with two 2026 papers that give the model a memory instead.

1. 1Transformer-XL2019
2. 2Longformer2020
3. 3Ring Attention2023
4. 4Mamba2023
5. 5Titans2025
6. 6Engram2026

All 110 papers, in 19 ladders →