Sparse and sliding-window attention

Full self-attention computes a score between every pair of tokens in the sequence. For a sequence of length N, this produces N² attention scores per head per layer. At N = 128K tokens with 32 heads across 32 layers, that's $128000^{2} \times 32 \times 32 = 16.8 \text{trillion}$ multiply-accumulate operations just for the attention logits — before the value projection. The KV cache grows linearly with N per layer, but the compute grows quadratically. Sparse attention restricts which token pairs interact, replacing O(N²) with a structured subset that preserves most of the model's representational power.

Sliding window attention

Each token attends only to the W most recent tokens in the sequence. Token at position t computes attention over positions [max(0, t - W + 1), t]. The attention mask is a band matrix of width W along the diagonal.

The computational cost drops from O(N²) to O(NW). For Mistral 7B (Jiang et al. 2023) with W = 4096 and a 32K context: full attention would require 32768² = 1.07 billion scores per head, while sliding window requires $32768 \times 4096 = 134 \text{million}$ — an 8x reduction at this context length. The ratio improves as N grows: at 128K context, it's 31x.

The KV cache benefit is equally important for inference. In standard attention, the KV cache grows with every generated token — at 128K context with GQA-8, Llama 3 8B stores approximately 4 GB of KV entries. With a sliding window, the cache is capped at W entries regardless of how long the generation runs. Mistral 7B's KV cache never exceeds $4096 \times 2 \times 4096 \times 32 \times 2 \text{bytes} = 2 \text{GB}$ (W entries × key+value × head_dim × num_kv_heads × float16), even at 128K context.

Information propagation across layers

A single sliding window layer can only propagate information W tokens backward. But stacked layers compound the receptive field: after L layers, each token has an effective receptive field of L × W tokens. Mistral 7B with 32 layers and W = 4096 has a theoretical receptive field of $32 \times 4096 = 131, 072$ tokens — covering the full 128K context through indirect attention paths.

This is weaker than direct attention. Information that passes through multiple layers undergoes repeated compression and transformation. A token at position 100K cannot directly attend to position 0 in any single layer — it relies on intermediate tokens carrying that information forward through the stack.

Implementation

A sliding window mask is a boolean tensor where position (i, j) is True if i - W < j <= i:

python

import torch
import torch.nn.functional as F

def sliding_window_attention(
    Q: torch.Tensor,  # (batch, heads, seq_len, head_dim)
    K: torch.Tensor,
    V: torch.Tensor,
    window_size: int = 4096
) -> torch.Tensor:
    batch, heads, seq_len, head_dim = Q.shape
    scale = head_dim ** -0.5

    # Full attention scores
    scores = torch.matmul(Q, K.transpose(-2, -1)) * scale  # (batch, heads, seq_len, seq_len)

    # Sliding window mask: each token attends to at most window_size previous tokens
    row_idx = torch.arange(seq_len, device=Q.device).unsqueeze(1)
    col_idx = torch.arange(seq_len, device=Q.device).unsqueeze(0)
    mask = (col_idx <= row_idx) & (col_idx > row_idx - window_size)

    scores = scores.masked_fill(~mask, float('-inf'))
    attn_weights = F.softmax(scores, dim=-1)
    return torch.matmul(attn_weights, V)

This naive implementation still materializes the full N×N score matrix. In practice, FlashAttention-2 (Dao 2023) supports sliding window natively — it simply skips computing tiles outside the band, achieving true O(NW) compute and O(N) memory.

When sliding window fails

Tasks requiring arbitrary long-range dependencies degrade under sliding window attention. Consider "summarize the conclusion of this 100-page document, noting how it references the introduction." If the introduction is at position 0 and the conclusion starts at position 90K, a model with W = 4096 cannot directly connect these regions in any single layer. The information must survive propagation through ~22 intermediate layers — each step lossy.

Empirically, Mistral 7B (W = 4096) underperforms Llama 2 7B (full attention) on the "passkey retrieval" task at distances beyond 16K tokens (Jiang et al. 2023, Table 3). For most natural language tasks — where relevant context is predominantly local — the quality difference is negligible.

Block-sparse attention: BigBird

BigBird (Zaheer et al. 2020) combines three attention patterns to maintain global connectivity while keeping compute at O(N):

Local window — each token attends to W neighbors (same as sliding window)
Random connections — each token attends to R randomly selected tokens from anywhere in the sequence
Global tokens — G designated tokens attend to (and are attended by) every token in the sequence

The total attention cost per token is W + R + G instead of N. BigBird uses W = 3 × block_size (typically block_size = 64, so W = 192), R = 3 random blocks, and G = 2 global blocks. This maintains O(N) complexity while preserving a theoretical guarantee: the resulting attention graph has the same expressive power as a full graph (any node can reach any other node in constant hops through the global tokens).

Global tokens as information bottlenecks

The G global tokens serve as a shared memory bus. Every token writes information to the global tokens, and every token reads from them. For tasks like document classification or question answering, the [CLS] token or question tokens are designated as global — they aggregate information from the entire sequence without requiring full pairwise attention.

Longformer attention

Longformer (Beltagy et al. 2020) uses a similar structure to BigBird but makes the design choices explicit for NLP tasks:

Sliding window — all tokens use local attention with W = 512 (configurable per layer, wider in upper layers)
Dilated sliding window — in some layers, attend to every k-th token within a wider range. With dilation factor d = 2 and window W = 512, the effective receptive field doubles to 1024 tokens while maintaining the same 512 attention operations per token
Task-specific global attention — the [CLS] token gets global attention for classification; question tokens get global attention for QA; no global tokens for language modeling

Dilated sliding window

Standard sliding window with W = 512 covers 512 contiguous tokens. Dilated window with W = 512 and d = 2 attends to positions {t-1024, t-1022, t-1020, ..., t-2, t} — 512 attention operations covering a 1024-token span. The gaps are filled by heads with different dilation rates or by lower layers with non-dilated attention.

This mirrors dilated convolutions in WaveNet (van den Oord et al. 2016): stacking layers with increasing dilation rates builds exponentially growing receptive fields. Longformer uses this in lower layers (d = 1 to 4) and switches to standard sliding window in upper layers.

python

def dilated_window_mask(seq_len: int, window_size: int, dilation: int) -> torch.Tensor:
    """Create a dilated sliding window attention mask.

    Each token attends to window_size positions, spaced dilation apart.
    Effective receptive field = window_size * dilation.
    """
    positions = torch.arange(seq_len)
    row_idx = positions.unsqueeze(1)  # (seq_len, 1)

    # Generate offsets: -window_size*dilation to 0, step dilation
    half_w = window_size // 2
    offsets = torch.arange(-half_w, half_w + 1) * dilation  # (window_size+1,)

    # Attended positions for each token
    attended = row_idx + offsets  # (seq_len, window_size+1)

    # Build mask
    mask = torch.zeros(seq_len, seq_len, dtype=torch.bool)
    for i in range(seq_len):
        valid = attended[i]
        valid = valid[(valid >= 0) & (valid < seq_len)]
        mask[i, valid] = True

    # Apply causal constraint
    causal = torch.tril(torch.ones(seq_len, seq_len, dtype=torch.bool))
    return mask & causal

Comparing attention patterns on a retrieval task

The following demonstrates the quality difference between full and sparse attention on a synthetic "needle in a haystack" task — retrieving a specific fact embedded at a known position in a long context:

python

import torch
import torch.nn as nn
import torch.nn.functional as F

class SimpleAttentionLayer(nn.Module):
    def __init__(self, d_model: int = 256, n_heads: int = 8, window_size: int = None):
        super().__init__()
        self.n_heads = n_heads
        self.head_dim = d_model // n_heads
        self.window_size = window_size
        self.qkv = nn.Linear(d_model, 3 * d_model)
        self.out = nn.Linear(d_model, d_model)

    def forward(self, x: torch.Tensor) -> torch.Tensor:
        B, N, _ = x.shape
        qkv = self.qkv(x).reshape(B, N, 3, self.n_heads, self.head_dim)
        q, k, v = qkv.permute(2, 0, 3, 1, 4)  # each: (B, heads, N, head_dim)

        scores = torch.matmul(q, k.transpose(-2, -1)) / (self.head_dim ** 0.5)

        # Causal mask
        causal = torch.triu(torch.ones(N, N, device=x.device), diagonal=1).bool()
        scores.masked_fill_(causal, float('-inf'))

        # Sliding window mask (if specified)
        if self.window_size is not None:
            row = torch.arange(N, device=x.device).unsqueeze(1)
            col = torch.arange(N, device=x.device).unsqueeze(0)
            window_mask = col < (row - self.window_size)
            scores.masked_fill_(window_mask, float('-inf'))

        attn = F.softmax(scores, dim=-1)
        out = torch.matmul(attn, v)
        return self.out(out.transpose(1, 2).reshape(B, N, -1))


# Compare retrieval accuracy at varying distances
seq_len = 8192
d_model = 256

full_attn = SimpleAttentionLayer(d_model=d_model, window_size=None)
window_attn = SimpleAttentionLayer(d_model=d_model, window_size=512)

x = torch.randn(1, seq_len, d_model)

with torch.no_grad():
    full_out = full_attn(x)    # Can attend to any position
    win_out = window_attn(x)   # Can only attend to 512 recent positions

# Token at position 8000 trying to retrieve info from position 100:
# full_out[0, 8000] has direct access to position 100
# win_out[0, 8000] cannot see beyond position 7488 in this layer
print(f"Full attention: token 8000 attends over all 8001 positions")
print(f"Window attention: token 8000 attends over positions 7489-8000 only")

When to use each pattern

Sliding window (Mistral) works well for:

Chat and instruction-following (context is predominantly recent)
Code completion (references are usually within a few hundred lines)
Streaming inference where KV cache memory is the bottleneck

Block-sparse / Longformer works well for:

Long document understanding (papers, legal contracts, books)
Question answering over long contexts where question tokens need global access
Encoder-only models for classification/NER over long inputs

Full attention remains necessary for:

Tasks requiring precise retrieval of arbitrary facts across 100K+ tokens
Multi-document synthesis where relevant passages could be anywhere
Maximum quality on short-to-medium contexts (under 8K tokens) where O(N²) is affordable

The practical default in 2026: most production models use sliding window for long-context efficiency (Mistral, Phi-3) or combine it with a few full-attention layers at intervals (Gemma 2 alternates sliding window and full attention layers). The quality gap between sparse and full attention continues to narrow as architectures improve, but for tasks requiring guaranteed long-range retrieval, full attention — distributed via Ring Attention if necessary — remains the gold standard.

← Previous