Don't approximate — just attend less
If approximating softmax is hard, the alternative is to leave softmax exact and just attend to fewer tokens. The two early production winners are Longformer (Beltagy et al., 2020) and BigBird. Both use a combination of: a local sliding window (each token attends to its w neighbors), global tokens (a small set of designated tokens that attend everywhere and are attended to by everyone), and in BigBird's case, additional random connections.
The cost is O(n·w) where w is the window size. Linear in sequence length when w is fixed. The assumption is that most relevant information is local, with global tokens handling the rare long-range dependencies. For documents this works well; for tasks with arbitrary long-range dependencies, it loses information.
Sliding window in production: Mistral and Griffin
The version that actually shipped widely is sliding-window attention, used in Mistral 7B (window 4096), Mistral Large, and Google's Griffin family. Each layer attends only to a window of recent tokens; the model's stack-of-layers structure means information can still propagate further than the window because each layer's output feeds the next layer's window.
Mistral's architecture choice — sliding window 4096 with the model trained at higher context lengths — was a productionization of this idea, and it's a big reason Mistral's models punched above their parameter count for long context. Griffin (Google, 2024) combines sliding-window attention with a recurrent linear-RNN component, giving a hybrid that hit 6K tok/s vs. ~2K for Gemma at comparable scale.
Learned sparsity — NSA and MoBA
The 2025 generation of sparse attention got more interesting. NSA (Native Sparse Attention) and MoBA (Mixture of Block Attention), both ACL 2025 papers, use learned sparsity patterns: the model decides per-query which tokens are worth attending to, with sparsity constraints baked into the kernel for hardware efficiency.
Learned sparsity converges much closer to full-attention quality than fixed sparsity. The cost: the kernels are more complex than sliding window, and the patterns can be harder to debug. But the early production results (Moonshot's Kimi family uses this) are strong enough that NSA-style sparsity is likely the default sparse-attention pattern through 2027.