Efficient and Sparse Attention Mechanisms are architectural modifications and computational optimizations to the standard O(N²) self-attention mechanism that enable transformers to process longer sequences with reduced memory and compute — from algorithmic sparsity patterns (sliding window, dilated) to hardware-aware implementations (FlashAttention) to distributed approaches (Ring Attention) that extend context to millions of tokens.

Standard Attention Bottleneck

Attention(Q,K,V) = softmax(QK^T / √d_k) · V

For sequence length N, hidden dim d:
  QK^T: O(N² · d) compute, O(N²) memory for attention matrix
  N=128K tokens: attention matrix = 128K² = 16.4 billion entries

FlashAttention (Hardware-Aware Exact Attention)

FlashAttention (Dao et al., 2022) computes exact standard attention but restructures the computation to minimize GPU HBM (high-bandwidth memory) access:

Standard: Load full Q,K,V from HBM → compute N×N attention → store → multiply V
  Memory: O(N²) for attention matrix

FlashAttention: Tile Q,K,V into blocks that fit in SRAM (shared memory)
  For each Q-block:
    For each K,V-block:
      Compute partial attention in SRAM (fast)
      Update running softmax statistics (online softmax trick)
  Never materialize full N×N attention matrix in HBM
  Memory: O(N) — only store output O, running stats m and l

FlashAttention-2 further optimized parallelism (across seq_len in addition to batch/heads) achieving 50-73% of theoretical GPU FLOPs — 2× faster than FlashAttention and up to 9× vs. standard PyTorch attention.

Sparse Attention Patterns

Mistral/Mixtral Sliding Window Attention

Window size W = 4096
Each token attends to the W preceding tokens only:
  Token at position i attends to positions [max(0, i-W+1), i]
  
With L layers, effective receptive field = L × W
  (32 layers × 4096 window = 131K effective context)
KV cache size: O(W) per layer instead of O(N)

Ring Attention (Distributed Long Context)

N devices, each holds a segment of the sequence:
  Device 0: tokens [0, N/P)        Device 1: tokens [N/P, 2N/P)  ...

Each device holds its Q-block locally.
KV-blocks are passed in a ring:
  Step 1: Compute attention with local KV → send KV to next device
  Step 2: Compute attention with received KV → send to next → accumulate
  ... (P steps total)

Result: Each device computes full attention for its Q-block
Communication overlapped with computation → ~zero overhead
Context length scales linearly with number of devices

Ring Attention enabled >1M token contexts by distributing across devices.

Multi-Query and Grouped-Query Attention

MHA:  H query heads, H key heads, H value heads   (standard)
MQA:  H query heads, 1 key head,  1 value head     (minimal KV cache)
GQA:  H query heads, G key heads, G value heads     (G < H, balanced)
  Llama 2 70B uses GQA with G=8, H=64
  KV cache reduced by H/G = 8×

Efficient attention is the enabling technology for long-context AI applications — from FlashAttention's hardware-aware exact computation to sparse patterns to distributed Ring Attention, these techniques have extended practical context lengths from 2K tokens to 1M+, fundamentally expanding what transformer models can process and reason about.