Sliding Window Attention

The defining feature of Sliding Window Attention is that it imposes a hard, fixed upper bound on the size of the KV cache per layer. A token at position i can only attend to tokens in the range [i - w, i], where w is the window size. This means the cache for a single sequence grows to a maximum of w * layer_count * 2 tensors and then stops, regardless of total sequence length. This predictable, O(1) memory complexity is critical for serving stability and resource planning.

By limiting the attention span to a local window, the computational cost of the attention operation scales linearly (O(n)) with sequence length n, in contrast to the quadratic (O(n²)) scaling of full attention. For each new token generated during the decode phase, the model only computes attention scores against the w most recent cached keys and values. This makes processing very long documents or conversations computationally feasible.

A key trade-off of the sliding window is that information can only propagate w tokens per layer. For a model with L layers, the theoretical receptive field—the maximum distance a token can influence—is w * L. This can create a "bottleneck" for tasks requiring long-range dependency modeling. Architectures like Dilated Sliding Windows or hierarchical attention are sometimes layered on top to mitigate this limitation.

During autoregressive generation, the sliding window enables highly efficient cache updates. For each new token, the system:

• Computes and caches its new KV pair.
• Evicts the oldest KV pair from the cache (the token at position i - w - 1), following a First-In-First-Out (FIFO) policy. This results in a constant, low-overhead memory operation per generated token, avoiding the need for complex cache eviction policies required by other long-context methods.

Sliding Window Attention is the core mechanism behind models designed for streaming or infinite-length inputs. It allows a model trained on finite windows to generalize to sequences far longer than its training context. Frameworks like StreamingLLM leverage this property, often combining it with attention sink tokens (the first few tokens) to maintain generation stability over millions of tokens without retraining.

• vs. Full Attention: Full attention has quadratic compute/memory cost (O(n²)) and an unbounded KV cache. Sliding window is linear (O(n)) with a bounded cache.
• vs. Other Sparse Attention (e.g., BigBird): Other sparse patterns (global, random, block) may have irregular memory access patterns. The sliding window's contiguous, localized access is more hardware-friendly and simplifies cache-aware scheduling in batched inference scenarios.

A KV cache, or key-value cache, is a memory buffer used in transformer-based language models to store the computed key and value tensors from previous tokens during the autoregressive decoding phase. This eliminates the need to recompute these tensors for every new token, which is the primary source of inference latency reduction.

• Purpose: Stores historical context for efficient attention computation.
• Impact: Transforms attention complexity from O(n²) to O(n) during decoding.
• Challenge: Its size grows linearly with sequence length, becoming a major memory bottleneck.

PagedAttention is a memory management algorithm that organizes a model's KV cache into non-contiguous, fixed-size blocks or pages. Inspired by virtual memory in operating systems, it allows for efficient sharing and dynamic allocation of cache memory across requests in a batch.

• Key Innovation: Eliminates internal fragmentation in the KV cache.
• Primary Benefit: Enables highly efficient continuous batching by allowing sequences to occupy non-contiguous physical memory.
• System: This algorithm is the core of the vLLM inference serving engine.

These are attention variants designed to reduce the memory footprint of the KV cache.

• Multi-Query Attention (MQA): All query heads share a single key head and a single value head. This drastically reduces the size of the KV cache.
• Grouped-Query Attention (GQA): A hybrid approach where queries are grouped, and each group shares a single key and value head. It offers a tunable trade-off between the cache efficiency of MQA and the model quality of standard Multi-Head Attention.
• Use Case: Critical for serving very large models or supporting long contexts where cache memory is the limiting constraint.

Techniques for enabling finite-window models to handle infinite-length sequences.

• Attention Sink: The observation that the initial tokens (often the first few) receive disproportionately high attention scores. These tokens act as a stable "sink" for attention scores, preventing numerical instability in very long sequences.
• StreamingLLM: A framework that leverages the attention sink phenomenon. By always keeping these sink tokens in the KV cache (even as a sliding window moves), it allows models trained with a fixed window to generalize to much longer, streaming inputs without retraining.

Methods to reduce the memory footprint of the cache itself.

• Quantization: Storing the key and value tensors in a lower numerical precision (e.g., FP8 or INT8) instead of FP16/BF16. This directly reduces the memory bandwidth and capacity required.
• Compression: A broader category including pruning (removing less important cache entries) and other algorithms to store the cache in a more compact form.
• Trade-off: These techniques introduce a small quality degradation but can dramatically increase the effective context length or batch size possible on a given GPU.

The two fundamental stages of transformer inference, with distinct KV cache implications.

• Prefill Phase: The initial, compute-bound stage where the entire input prompt is processed in parallel. The model computes the initial KV cache for all prompt tokens.
• Decode Phase: The memory-bound, token-by-token generation stage. The model reads from the existing KV cache, attends to the context, predicts the next token, and appends the new token's K/V to the cache.
• Optimization Focus: Sliding window attention primarily optimizes the memory-bound decode phase by limiting the active cache size.