Sliding Window Attention
Sliding Window and Local Sparse Attention are attention patterns restricting each token to attend only to nearby context within fixed window size — reducing attention complexity from quadratic O(n²) to linear O(n·w) enabling efficient processing of very long documents (100K+ tokens) on single GPUs.
Sliding Window Attention Mechanism:
- Window Definition: each token at position i attends only to tokens in [i-w, i+w] range where w is window size (512-2048 typical)
- Attention Matrix Structure: creating banded diagonal matrix instead of full matrix — only w×n non-zero entries instead of n² entries
- Computational Complexity: reducing FLOPS from O(n²·d) to O(n·w·d) and memory from O(n²) to O(n·w) — linear in sequence length
- Implementation: using efficient kernels (NVIDIA FlashAttention) with row-wise masking — only 2-3x slower than single-head attention despite sparsity
- Receptive Field: w=512 provides receptive field enabling local reasoning within paragraph or sentence scope
Local Attention Patterns:
- Fixed Window: uniform window size across all positions — simplest, best for causal (left-to-right only) or bidirectional attention
- Dilated Window: attending to every k-th token in extended range (e.g., positions [i-2w, i, step=k]) — captures longer range dependencies
- Strided Attention: combining fine-grained local (w=128) with coarse-grained remote (stride=4, attending to every 4th token) — 2-level hierarchy
- Centered Window: attending to neighbors symmetrically around position i — useful for document encoding (BERT-style) where future context available
Longformer Architecture:
- Hybrid Approach: combining local windowed attention with task-specific global attention tokens — key tokens (CLS, document summary markers) attend globally
- Configuration: local window size w=512, 4 attention heads use global attention on special tokens — remaining 8 heads use sliding window
- Complexity: O(n·w) local + O(n·g) global where g is number of global tokens (g<<n) — typically 5-10 global tokens
- Performance: 92% accuracy of full Longformer with 2x speedup on long-document classification (WikiHop, TriviaQA datasets)
Contextual Limitations and Trade-offs:
- Context Fragmentation: large reasoning tasks requiring distant context (multi-hop reasoning, anaphora resolution) suffer degradation
- Information Loss: window size w=512 too small for 10K+ document understanding — important context gets excluded
- Benchmarking: 2-5% accuracy drop on tasks requiring long-range dependency modeling (question answering over documents)
- Adaptation Needed: models trained with sliding window have different inductive biases — fine-tuning required for efficient transfer
Implementation Techniques:
- Block-Sparse Attention: grouping tokens into blocks and computing block-level sparsity pattern — enables efficient GPU computation
- Composite Attention: interleaving sparse local windows with dense global projections — maintains expression capacity
- Efficient Kernels: CUDA kernels optimized for banded matrix multiplication — achieves 80-90% of theoretical FLOPS efficiency
- Autoregressive Masking: combining future token masking (causal) with window boundary masking — ensures no information leakage
Extended Sparse Patterns:
- Reformer Attention: using locality-sensitive hashing (LSH) to attend to k most similar tokens (k=64) regardless of distance
- BigBird: combining window attention, random attention, and global attention in single layer — O(n) complexity for full transformer
- Performer: using FAVOR+ kernel approximating softmax attention with random features — eliminates memory complexity entirely
- Sparse Transformer: using strided and fixed attention patterns alternating across layers — enables 65K token sequences
Long Document Processing:
- Llama 2 Extended: extending 4K context to 32K using ALiBi and sliding window enables efficient long-document processing
- LongLLaMA: fine-tuned Llama 2 with sparse attention supporting 256K tokens — 500x longer than standard 4K
- Longformer: BERT-scale models with 4096 token attention capacity — supports legal documents, research papers (2-5K pages)
- Sparse Llama: research variant using local attention + global tokens, achieving 32K context on single 80GB A100
Trade-off Analysis:
- Speed vs Quality: w=512 achieves 3x speedup but 2-3% accuracy loss — w=1024 achieves 1.5x speedup with <1% loss
- Memory vs Computation: sparse attention memory-bound (limited to 100-200GB/s bandwidth) vs compute-bound full attention
- Model Size Efficiency: sliding window enables scaling to 1T+ parameters (2048-4096 window) — Chinchilla optimal allocation favors longer context
- Hardware Utilization: sparse kernels achieve 60-70% peak FLOPS vs 40-50% for full attention on irregular patterns — selective sparsity beneficial
Practical Recommendations:
- Short Sequences (<8K): use full attention, sparse overhead negates benefits
- Medium Sequences (8K-64K): sliding window w=1024-2048 achieves 1.5-2x speedup with minimal quality loss
- Long Sequences (64K-256K): combining multiple sparse patterns (local + global) essential — single pattern insufficient
- Production Deployment: Longformer and BigBird proven in industrial use for document classification, semantic search at scale
Sliding Window and Local Sparse Attention are critical for processing long documents — enabling efficient processing of academic papers, books, and code repositories that exceed standard transformer context limits while maintaining reasonable model quality.