Attention Algorithms 2017-2026: MHA, GQA, MLA, NSA Selection Guide

1. Origin: Why Standard Attention Is O(n²)

In 2017, Vaswani et al. (NeurIPS 2017, arXiv:1706.03762) introduced Scaled Dot-Product Attention with Multi-Head Attention (MHA) . It computes Q·Kᵀ scores, applies softmax, and weights V. The cost: the score matrix is O(n²), and KV cache grows O(n). During decoding, each new token requires reading the entire KV cache from memory—tensor cores compute in microseconds, then stall on memory bandwidth, making long generation expensive.

Classic and optimized attention algorithms

2. Battlefield 1: Compressing KV Cache (Memory/Decoding Optimization)

These methods keep the attention computation unchanged but reduce how much K/V each head stores.

MQA (Multi-Query Attention) (Shazeer, 2019, "Fast Transformer Decoding"): All heads share a single K/V set, reducing KV cache to ~10% of MHA, at the cost of reduced head diversity.

GQA (Grouped-Query Attention) (Ainslie et al., 2023, arXiv:2305.13245): Groups of heads share K/V, a compromise between MQA and MHA. With 4 groups, cache is ~37% of MHA. Now standard in LLaMA 2/3, Mistral, Qwen, etc.

MLA (Multi-Head Latent Attention) (DeepSeek-V2, May 2024, arXiv:2405.04434): Uses low-rank joint compression —K/V are compressed into a small latent vector for storage, then projected back to per-head K/V at inference. This "compress storage, use fully" approach reduces KV cache to ~2% of MHA with near-lossless quality. Adopted by DeepSeek-V3/R1, Kimi K2, GLM-5.

Key distinction: MQA/GQA save by sharing heads, losing diversity; MLA saves by low-rank compression, losing almost nothing.

3. Battlefield 2: Accelerating Exact Attention (I/O Optimization, Numerically Identical)

This line is often misunderstood: FlashAttention is not an approximation—it is mathematically equivalent to standard attention , only reordering computation.

FlashAttention (Tri Dao, 2022): Tiling + recomputation keeps intermediate matrices in on-chip SRAM, avoiding HBM writes. Memory drops from O(n²) to O(n), 2–4× speedup over naive implementation.

FlashAttention-2 (2023): Optimized parallelism and work partitioning, supports MQA/GQA, achieves 50%–73% peak FLOPS on A100.

FlashAttention-3 (July 2024, Tri Dao + Princeton + Together AI): Targets Hopper (H100). Async warp specialization, native FP8, interleaved matmul and softmax. FP16 1.5–2.0× faster than FA2 (740 TFLOPS, 75% utilization); FP8 near 1.2 PFLOPS.

FlashAttention-4 (early 2026): Targets Blackwell (B200), 1605 TFLOPS in BF16 (71% utilization).

PagedAttention (vLLM, Kwon et al., 2023): Manages KV cache like OS paging, eliminating memory fragmentation; foundation of modern LLM inference serving.

4. Battlefield 3: Extending Long Context (Sparse/Window)

Standard attention attends to all history, too costly. These methods selectively attend to a subset.

Sliding Window Attention (SWA) : Attends only to recent tokens. Used in Mistral 7B; Gemma 3 (1024 window), GPT-OSS (128 window) use hybrid window+global.

Classic Sparse Attention : Longformer, BigBird (2020) use block-sparse + global tokens; Performer (2020, FAVOR+), Linformer (2020) use random features/low-rank to reduce attention to linear complexity.

StreamingLLM (2023): Uses "attention sinks" to retain initial tokens, enabling infinite-length streaming generation.

Note: Sparse/linear attention are approximations that lose information; FlashAttention is exact , just faster. Do not conflate them.

2025–2026 frontier attention and alternative architectures

5. Frontier: 2025–2026 (Key Focus)

Since 2025, the focus shifted from "optimizing attention" to "redesigning memory." Three representatives:

NSA (Native Sparse Attention) (DeepSeek, arXiv:2502.11089, Feb 2025, ACL 2025 Best Paper ): Hardware-aligned + natively trainable. Three parallel branches: compression branch (coarse global), selection branch (top-K fine-grained blocks by compression scores), sliding window (local). Uses Triton kernels + group-centric data loading to turn theoretical sparse speedups into real wall-clock gains. On a 27B MoE with 64k context, measured forward 9×, backward 6×, decode 11.6× speedup on H800. DeepSeek productized this as DSA in V3.2-Exp (Sep 2025) and V4 series.

MoBA (Mixture of Block Attention) (Moonshot/Kimi, arXiv:2502.13189, 2025, NeurIPS 2025): Splits context into blocks, uses parameter-free top-K gating to route each query to a few blocks, routing memory like MoE, while remaining compatible with full attention.

DSA : DeepSeek's productized version of NSA ideas (V3.2-Exp / V4).

More radical: replacing softmax attention entirely:

Linear Attention : Removes softmax, collapses attention to fixed-size recurrent state. Representatives: MiniMax-01's Lightning Attention (Jan 2025, 7:1 linear:global, 456B MoE, 4M context), Gated DeltaNet / GLA , RWKV-7.

State Space Models (SSM) : Replace attention with selective linear recurrence. Representatives: Mamba / Mamba-2 (2024, SSM duality), Mamba-3 (ICLR 2026).

Test-Time Memory : Google Titans (Dec 2024) uses gradient-based "surprise" signals to update long-term neural memory, exceeding 2M context; TTT (Test-Time Training) treats hidden state as weights, updates online with SGD.

Hybrid Architectures (current true frontier) : Pure linear/SSM haven't yet won general language modeling, so mainstream becomes "few exact attention layers + many cheap layers". Examples: MiniMax-01 (7:1), Qwen3-Next (Gated DeltaNet + Attention 3:1), Kimi Linear (KDA + MLA 3:1), Jamba (Mamba + Attention), Gemma 3 (SWA + Attention 5:1).

One-sentence summary of the frontier: 2025–2026 consensus is "hybrid architectures"—keep global attention where precise recall is needed, replace the rest with cheaper linear/sparse/recurrent layers.

6. Selection Guide: Which One Should You Use?

Run open-source models, no hassle : Default to GQA + FlashAttention; frameworks have it built-in, zero effort.

Train/deploy yourself, memory tight, need long context : Choose MLA (e.g., DeepSeek family) or GQA; KV cache shrinks dramatically.

Ultra-long documents / Agent memory : Look at models with sparse or hybrid architectures (NSA/DSA family, Kimi Linear, Qwen3-Next).

Maximum throughput, long generation : FlashAttention-3/4 (H100/B200) + PagedAttention (vLLM).

Research new architectures : Linear attention (Gated DeltaNet), SSM (Mamba-3), Titans/TTT are the hottest directions.

Attention algorithm selection cheat sheet

Conclusion

Attention has grown from a single 2017 formula into a family of 20+ algorithms. The main thread remains clear: compress KV cache, accelerate exact attention, extend long context, finally converge on hybrid architectures . Instead of asking "which attention is strongest," ask "for my scenario, which class of optimization hurts most."