Longformer

The core innovation of the Longformer replaces full quadratic self-attention with a fixed-size windowed attention pattern. Each token attends only to w/2 tokens on each side, where w is the window size.

• Linear Complexity: Computational cost scales as O(n × w) instead of O(n²), making it feasible to process sequences of 4,096+ tokens.
• Stacked Receptive Field: By stacking multiple Longformer layers, the effective receptive field grows. After L layers, a token can incorporate information from up to L × w/2 tokens away.
• Dilated Windows: The architecture can use dilated sliding windows with gaps between attended tokens, dramatically increasing the receptive field without additional compute cost.

This pattern is ideal for tasks where local context is paramount, such as named entity recognition and coreference resolution.

To complement the local sliding window, Longformer designates a small set of input positions for task-motivated global attention. These special tokens attend to the entire sequence and are attended to by all other tokens.

• Symmetric Global Attention: Global tokens have full visibility across the entire input, enabling them to act as information aggregation points.
• Task-Specific Designation: For classification, the [CLS] token is made global. For question answering, all question tokens are made global, allowing the model to condition answer span prediction on the full question context.
• Flexible Configuration: The global attention pattern is defined by a binary mask, allowing developers to specify exactly which tokens require full context for a given downstream task.

This hybrid approach preserves the ability to model long-range dependencies for critical task-specific elements while maintaining linear efficiency for the bulk of the document.

Standard Transformer implementations are heavily optimized for dense matrix multiplications. The Longformer's sparse attention pattern requires custom CUDA kernels to achieve practical speedups.

• Sparse Matrix Multiplication: The authors implemented a custom CUDA kernel that performs the attention computation only on the non-zero entries of the sparse attention mask, avoiding wasted computation on masked-out positions.
• Band Matrix Operations: The sliding window pattern forms a band matrix, which can be computed efficiently using specialized linear algebra routines.
• TVM Implementation: The original implementation used Apache TVM, a deep learning compiler stack, to generate optimized GPU code for the specific sparsity pattern.

Without these low-level optimizations, the theoretical linear complexity would not translate to wall-clock speed improvements over highly optimized dense attention implementations.

Longformer adapts its attention pattern for causal language modeling tasks, where each token can only attend to previous positions to prevent information leakage from the future.

• Causal Dilated Sliding Window: The window is restricted to only preceding tokens, with dilation patterns that increase the receptive field without violating the autoregressive property.
• Staged Training Procedure: The model is typically initialized from a pre-trained RoBERTa checkpoint, then fine-tuned with progressively longer sequences and dilated windows to learn effective long-range representations.
• Attention Sink Stability: Like other long-context models, the initial tokens act as attention sinks, absorbing disproportionate attention weights and stabilizing the softmax distribution across very long sequences.

This enables Longformer to generate coherent text and perform document-level understanding tasks that require tracking entities and events across thousands of tokens.

Longformer was evaluated on tasks that require synthesizing information across long documents, demonstrating significant improvements over chunking-based approaches.

• WikiHop: Achieved state-of-the-art results on this multi-hop reading comprehension dataset by processing entire documents as single sequences rather than splitting them into overlapping chunks.
• Hyperpartisan News Detection: Outperformed previous methods by attending to long-range stylistic and structural patterns across full articles.
• TriviaQA: Demonstrated strong performance on distant supervision question answering by conditioning answer extraction on complete evidence documents.
• IMDB Review Classification: Showed that global attention on the [CLS] token effectively aggregates sentiment signals across very long movie reviews.

The key insight is that end-to-end processing of long documents avoids the information fragmentation inherent in sliding window or chunking approaches used by earlier models.

Training Longformer on very long sequences requires careful memory management. The architecture leverages gradient checkpointing to trade compute for memory.

• Activation Recomputation: Instead of storing all intermediate activations for the backward pass, only a subset of layer outputs are kept in memory. The rest are recomputed on-the-fly during backpropagation.
• Selective Checkpointing: Only the memory-intensive attention layers are checkpointed, while cheaper feed-forward layer activations are retained normally.
• Mixed Precision Training: Combined with FP16 floating point, the memory savings from checkpointing enable training on sequences up to 4,096 tokens on standard GPU hardware.

This technique is essential for making the linear complexity gains of the sparse attention pattern practically realizable during the training phase, not just inference.

The primary mechanism enabling Longformer's linear complexity. Instead of attending to every token, each token attends only to a fixed-size window of w/2 tokens on each side. This local attention pattern reduces the O(n²) complexity of standard self-attention to O(n × w), where w is the window size. Crucially, this is implemented as a banded matrix multiplication, making it highly efficient on modern GPU hardware. Stacking multiple such layers allows information to flow across the full sequence through successive local interactions, akin to a convolutional receptive field.

A complementary mechanism where a small set of pre-selected tokens attend to the entire sequence, and all tokens attend to them. This creates information highways that bypass the slow propagation of local attention. Global tokens are typically task-specific:

• Classification: The [CLS] token
• QA: All question tokens
• Language Modeling: Special tokens like [MASK] This hybrid pattern preserves the model's ability to build task-specific, full-context representations without sacrificing the efficiency of local attention for the bulk of the sequence.

An extension of the sliding window that introduces gaps between attended tokens, exponentially increasing the receptive field without increasing computation. A dilation rate of d means the window skips d-1 tokens between each attended neighbor. By stacking layers with progressively larger dilation rates, the model achieves a geometrically expanding receptive field—reaching sequence lengths of thousands of tokens in just a few layers. This is directly inspired by dilated convolutions in WaveNet and is critical for tasks requiring extremely long-range dependencies.

Longformer's attention is defined by a sparse, customizable attention mask that combines sliding window and global patterns into a single matrix. The implementation uses custom CUDA kernels for banded matrix multiplication and sparse operations, avoiding the materialization of the full n×n attention matrix. This allows the model to scale to documents of 4,096 tokens and beyond on standard GPU memory, compared to the 512-token limit of BERT-base. The pattern is fixed per task, not learned, ensuring deterministic and predictable memory usage.

Longformer-Encoder-Decoder (LED) adapts the architecture for sequence-to-sequence tasks like summarization. The encoder uses the efficient local+global attention, while the decoder employs a causal sliding window—each token attends only to previous tokens within its window. This enables processing input documents of up to 16K tokens while generating summaries. The model initializes from BART weights, with the attention pattern being the only architectural change, proving the pattern's plug-and-play compatibility with existing Transformer designs.

Longformer is agnostic to the position encoding scheme. The original implementation uses learned absolute position embeddings initialized from a pre-trained RoBERTa checkpoint, but the attention pattern is fully compatible with relative position encodings like RoPE or ALiBi. This flexibility allows Longformer-style attention to be retrofitted into modern architectures. The key constraint is that the position embedding matrix must be sized to accommodate the maximum target sequence length, which is a one-time memory allocation.