Longformer & Big Bird

The Problem

The original Transformer architecture computes self-attention between every pair of tokens in a sequence. This mechanism requires calculating an $N \times N$ attention matrix, where $N$ is the sequence length. This $O(N^2)$ quadratic complexity in both memory and compute means that standard Transformers hit a hard ceiling around 512 or 1024 tokens.

For long documents, books, or lengthy codebases, processing text required chunking it into smaller, isolated segments. This destroyed cross-segment context and made long-range reasoning fundamentally impossible without expensive hierarchical workarounds.

The Idea

Instead of every token attending to every other token, we can use a sparse attention pattern. Most tokens only need to look at their immediate neighbors to understand local grammar and syntax, while a small number of special tokens can look at the entire sequence to build a global representation.

By dropping the vast majority of attention connections, the $O(N^2)$ complexity is reduced to $O(N)$ linear complexity, allowing the model to process sequences of 4,096 to 16,384 tokens or more on the same hardware. Longformer and its close cousin Big Bird mathematically proved that combining random attention, windowed attention, and global attention is theoretically Turing-complete and preserves the representational power of full, dense attention.

How It Works

Both Longformer and Big Bird build a sparse attention matrix using distinct types of connections:

Sliding Window Attention (Local) A token only attends to a fixed number of tokens to its left and right (e.g., $w=512$). This builds local context, operating much like a 1D convolution. It ensures that every word understands its immediate surrounding sentence or paragraph.

Global Attention A few specific tokens (like the [CLS] token for classification, or question tokens in QA tasks) are designated as "global". These global tokens attend to every other token in the sequence, and every other token attends to them. This provides a central hub for document-level representations.

Dilated or Random Connections To help information flow across the long document without requiring many hops through the local window, Longformer uses dilated sliding windows (skipping tokens to increase the receptive field without adding compute). Big Bird goes a step further by using random attention (each token attends to a few randomly chosen tokens across the sequence). This drastically reduces the shortest-path distance between any two tokens in the sequence graph.

Why It Mattered

These architectures provided the first viable blueprint for processing thousands of tokens at once without resorting to recurrent architectures (like LSTMs) or hierarchical chunking. They proved that dense, all-to-all attention was largely redundant for natural language, paving the way for the era of long-context models.

What Came After

While sparse attention patterns were highly influential theoretically, they required custom, complicated CUDA kernels to be efficient, as standard GPUs are heavily optimized for dense matrix multiplications.

The field eventually shifted toward exact attention optimizations like FlashAttention (which computes full $O(N^2)$ attention much faster and with less memory via hardware-awareness) and architectures like Mamba or RWKV that natively compress context. However, the insight that attention can be sparsified remains crucial in modern extreme-context architectures like Ring Attention, Sparse MoE models, and block-sparse patterns.