Attention Mechanisms

Let attention specialize. Instead of one big attention over the whole d_model space, run H independent attention heads in lower-rank subspaces and concatenate — each head free to learn a different relation type.

Replace dense O(T²) attention with structured sparsity — two fixed patterns (strided and fixed) that together let any pair of tokens reach each other in at most two hops while attending to only O(T·√T) total keys.

Cut the KV cache by H× — share a single K, V across all H query heads. Solves decoder-side inference memory pressure that MHA's per-head cache creates.

Replace dense O(N²) attention with locality-sensitive hashing — bucket similar Q, K together and only attend within buckets. O(N · log N) attention, learnable rather than fixed sparsity pattern.

Make per-layer attention compute and KV cache scale linearly with sequence length instead of quadratically — by restricting each query to a fixed window of recent keys.

Replace softmax with a kernel that lets you reorder QKV multiplications — making attention compute linear in sequence length, with a constant-size recurrent state at autoregressive inference.

Project keys and values down to a fixed low-rank subspace before attention — making attention O(N) by replacing the N×N attention matrix with an N×k one, where k is a fixed projection rank.

Combine three structured sparse-attention patterns (random, window, global) so the model preserves universal-approximation properties while running in O(N) attention. The first theoretically-grounded sparse attention with a Turing-completeness proof.

Approximate softmax attention with random features that decompose the kernel — letting attention scale linearly in sequence length while remaining an unbiased estimator of the original softmax operator.

Compute exact attention 2–4× faster and with 5–20× less peak memory by recognizing that attention is memory-bandwidth-bound and tiling the computation to keep operations on-chip.

Get most of Multi-Query Attention's KV-cache savings without the quality drop — by sharing K, V across small groups of query heads instead of all heads.

Make linear attention actually fast at moderate sequence lengths by tile-fusing the computation so the constant overhead of the linear recurrence doesn't dominate against optimized FlashAttention kernels.

Cut KV cache memory below MQA/GQA while preserving or improving quality.

Push attention compute below MLA's already-low cache floor by routing each query to a small top-K subset of historical keys, selected by a lightweight learned indexer.