LLM’s Billion Dollar Problem

Quick Overview

The core problem with scaling attention mechanisms, as demonstrated by linear attention models failing retrieval tasks over long contexts and the poor real-world performance of models relying solely on linear attention variants, is that the quadratic complexity of standard attention ($O(N^2)$) is necessary for true context-dependent reasoning across the entire sequence, while the $O(N)$ complexity of linear attention leads to information decay and poor performance on long-context retrieval benchmarks, forcing hybrid approaches like those in DeepSeek and MiniMax to interleave standard attention layers or use specialized linear variants like MLA/KDA to balance efficiency and performance.

Key Points: Standard self-attention complexity scales quadratically ($O(N^2)$) with sequence length ($N$), causing memory/compute issues for long contexts. Linear attention methods scale linearly ($O(N)$) by accumulating state in structured shared memory, making them efficient but prone to information decay over long contexts (e.g., linear attention failing to recall a password hidden at token #200,000 in a 250k context). Hybrid approaches like MiniMax/Hybrid interleave Standard and Linear attention layers, while DeepSeek uses only Multi-Head Latent Attention (MLA) layers, which is a gated linear variant. MiniMax-M1, using a hybrid of Lightning Attention (linear) and Full Attention (standard), achieved near 100% performance on the SCR benchmark at 1M context, significantly outperforming pure linear attention models like Kimi Linear. The high cost of standard attention is why linear attention was explored, but its lack of non-linearity (like Softmax) and reliance on cumulative state caused performance degradation on complex reasoning tasks. DeepSeek-V3.2 uses DeepSeek Sparse Attention (DSA), which reduces complexity by only attending to a fixed top-k set of tokens, achieving better long-context performance than pure linear methods like Qwen3-235B-A22B (228) in certain benchmarks.