Longformer,
explained.

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: in some attention heads or layers, the window has gaps, so it reaches further for the same number of connections — like looking at every other token instead of every adjacent one. A few dilated heads dramatically extend the range at no extra cost, while non-dilated heads keep the fine-grained local view. The receptive field ends up large enough for long-range reasoning while the per-layer cost stays 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.

By breaking the quadratic wall, Longformer let transformers operate at document scale — thousands of tokens instead of hundreds:

Before Longformer, handling a long document meant awkward workarounds — truncate it, split it into chunks and stitch results, or lose cross-chunk context. Longformer let a single model read the whole thing, which is qualitatively different for tasks where the answer depends on connecting distant parts.

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 + dilation + global tokens — 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.