Sliding Window Attention

The core efficiency gain of sliding window attention is its reduction in computational cost. Standard self-attention scales quadratically (O(n²)) with sequence length n. By limiting each token to attend to only w previous tokens (the window size), the complexity becomes linear (O(n * w)). For a fixed window size w, this is O(n), enabling the processing of extremely long sequences that are infeasible for dense transformers.

• Key Mechanism: Each position i computes attention scores only for positions in the range [i - w, i].
• Practical Impact: This allows models like Longformer and Mistral 7B to handle context lengths of 32k+ tokens or more with manageable memory and compute requirements.

This pattern is exceptionally effective at capturing local dependencies, which are dominant in many linguistic and structured data patterns. Most relevant information for predicting the next token or understanding a phrase is found within a nearby context.

• Inductive Bias: It encodes the prior that closer tokens are more relevant, mirroring the locality principle common in convolutional neural networks (CNNs) for vision.
• Use Case Strength: Excels in tasks where local coherence is paramount, such as syntactic parsing, named entity recognition, and local discourse modeling. It can struggle with tasks requiring direct long-range token-to-token relationships, which may require complementary mechanisms like global attention.

Unlike some dynamic sparse attention methods, the classic sliding window employs a fixed window size w that is a hyperparameter set before training. This simplicity is a key engineering advantage.

• Deterministic Pattern: The attention pattern is static and known in advance, allowing for highly optimized implementations using banded matrix operations or causal masking with a fixed offset.
• Trade-off: A small window maximizes speed but may miss necessary long-range context. A large window improves context at a linear computational cost. Models often use a hierarchical approach, combining local windows with occasional global attention (e.g., on [CLS] tokens) for document-level tasks.

Sliding window attention provides major benefits during text generation (autoregressive inference). It enables a fixed-size key-value (KV) cache, which is critical for deployment.

• KV Cache Mechanism: In a standard transformer, the KV cache grows linearly with the generated sequence length, consuming unbounded memory. With a window size w, only the keys and values for the last w tokens need to be cached and updated per generation step.
• Constant Memory Footprint: The memory requirement for the KV cache becomes O(w * batch_size * d_model), which is constant regardless of total sequence length. This enables sustained generation speed and makes long-context inference practical on memory-constrained hardware.

Technically, sliding window attention is implemented by modifying the standard causal attention mask. Instead of a mask that allows attention to all previous tokens, a banded mask is applied.

• Mask Structure: For a sequence of length n and window w, the attention mask M is defined as M[i, j] = 0 (allow) if i - w <= j <= i, else M[i, j] = -inf (block). This creates a band of width w along the diagonal of the attention matrix.
• Hardware Optimization: This banded structure allows for the use of specialized, efficient kernels (e.g., FlashAttention with sliding window support) that avoid computing the full n x n attention matrix, leading to significant speedups in both training and inference.

Sliding window attention is a foundational instance within the broader family of efficient transformer and sparse attention architectures.

• Comparison to Dilated/Strided Attention: Unlike dilated attention, which attends to tokens at exponentially increasing intervals, the sliding window provides contiguous local context, which is often more linguistically natural.
• Comparison to Block-Sparse Attention: It can be viewed as a special case of block-sparse attention where each block is a contiguous local sequence. It is simpler and more regular than random or learned sparse patterns.
• Common Extensions: It is frequently combined with:
  • Global Tokens: Adding a few tokens that attend to/are attended by all tokens (e.g., Longformer).
  • Hierarchical Windows: Using larger windows at higher layers of the network to build a "pyramid" of context.

While primarily using Rotary Positional Embedding (RoPE) for full attention, the release of Llama 2 included significant research and community-driven adaptations using grouped-query attention (GQA) which, when combined with later SWA implementations, informed efficient inference strategies. Its architecture demonstrated the trade-offs between pure SWA and other efficient attention methods, highlighting SWA's strength in streaming or very long-context scenarios where strict locality is acceptable.

SWA is critical in audio and speech processing models like Jukebox and AudioLM. Here, the extremely long sequences of audio samples (e.g., >1 million timesteps) make quadratic attention impossible. These models apply sliding windows over the raw waveform or latent audio tokens, allowing them to generate coherent, long-form audio by ensuring each step has sufficient local acoustic context, typically spanning several seconds of audio.

Dense passage retrievers like DPR and their successors often use a sliding window over documents at index time. They chunk a long document into overlapping windows, encode each window independently, and pool the embeddings. This approach:

• Preserves local coherence within each chunk.
• Captures information from all parts of a long document.
• Enables efficient similarity search against fixed-length window embeddings, a crucial pre-processing step for Retrieval-Augmented Generation (RAG) systems handling long contexts.

A broad class of transformer model variants designed to reduce the quadratic O(n²) computational and memory complexity of standard self-attention with respect to sequence length. This umbrella term includes methods like Sliding Window Attention, Linear Attention, and hashing-based approaches (e.g., Reformer). The core goal is to enable the processing of longer sequences, which is critical for document-level NLP and multimodal tasks, without prohibitive compute costs.

A class of attention mechanisms that reformulate the standard softmax(QKᵀ)V computation to achieve linear O(n) complexity. Instead of computing the full attention matrix, they often use kernel feature maps to decompose the operation, leveraging the associative property: (φ(Q) φ(K)ᵀ) V = φ(Q) (φ(K)ᵀ V). While mathematically elegant and highly efficient for very long sequences, they can trade off some expressiveness or require careful kernel design to match the performance of standard attention on certain tasks.

An attention mechanism that strikes a balance between quality and memory efficiency. It groups multiple query heads to share a single key head and value head. This is a generalization between Multi-Head Attention (MHA) and Multi-Query Attention (MQA).

• Benefit: Significantly reduces the size of the KV cache during autoregressive inference compared to MHA, lowering memory bandwidth pressure.
• Use Case: Adopted by models like Llama 2 and 3 for efficient large-scale inference, as it mitigates the quality degradation sometimes observed with pure MQA.

An I/O-aware, exact attention algorithm that dramatically speeds up training and inference. Its core innovation is avoiding the materialization of the large, intermediate attention matrix (size n x n) in slow High Bandwidth Memory (HBM).

• Mechanism: It recomputes attention scores on-the-fly within fast SRAM using tiling and recomputation techniques.
• Impact: Delivers 2-4x speedup and reduces memory usage from O(n²) to O(n), enabling longer context windows. It is a foundational optimization that can be combined with sparse patterns like sliding windows.

A paradigm where a neural network dynamically activates only a subset of its computational pathways based on the input. The goal is to achieve high model capacity with sub-linear average cost per example.

• Examples: Mixture of Experts (MoE), Early Exiting, and adaptive depth/width networks.
• Relation to Sliding Window: While sliding window is a fixed, structural sparsity pattern, conditional computation is input-adaptive. They are complementary efficiency strategies; a model could use sliding window attention and conditionally activate experts within each layer.

A positional encoding method that enables length extrapolation. Instead of adding positional embeddings, ALiBi adds a fixed, non-learned bias penalty to attention scores based on the distance between tokens.

• Key Feature: The bias decays linearly with distance, discouraging long-range attention. This inherently biases the model towards local contexts, similar to the inductive bias in Sliding Window Attention.
• Advantage: Models trained with ALiBi can generalize to sequence lengths much longer than those seen during training, a crucial capability for production systems.