Posts tagged "efficiency"
10 posts found
The Kernel Zoo: Performers, Fast Weight Programmers, and the Capacity-Approximation Tradeoff in Linear Attention
How to choose the feature map φ in linear attention — the capacity bound that says a state of dimension d_φ stores at most d_φ orthogonal key-value pairs, the Performer's FAVOR+ that approximates softmax with positive orthogonal random features, the DPFP map that grows capacity deterministically through ReLU-gated quadrant projections, and the capacity-versus-approximation tradeoff that defines the design space, with the linear-attention recurrence reframed as a 1990s fast weight programmer.
Mamba and Mamba-2: Selective State Spaces and Structured State Space Duality
Building Mamba and Mamba-2 from scratch — why fixed-dynamics state space models cannot do content-based reasoning, how the selection mechanism fixes it, and the structured-matrix duality showing every selective SSM is masked attention in disguise.
DeepSeek Sparse Attention: Learned Token Selection from Scratch
Letting the model choose its own sparse pattern — a lightweight indexer scores every past token, top-k selects the keys that matter for this query, and two-stage training with KL alignment keeps the sparse model faithful to its dense teacher at $O(nk)$ cost.
Gated Attention: Replacing Residuals and ReLU with Learned Gates
Building gated transformer blocks from the ground up — why standard residual connections and ReLU activations leave performance on the table, identity map reordering (pre-norm), five gating variants from input gating to GRU-type gates, gated identity initialization, GLU and its variants (SwiGLU, GEGLU, ReGLU, Bilinear), the 2/3 parameter budget trick, and the unified view of gating as multiplicative control — all derived step by step with a 4-dimensional running example.
Targeted Memory: The Delta Rule, Gated DeltaNet, and Kimi Delta Attention
Building targeted memory for linear attention from scratch — the delta rule (erase only the key being overwritten, derived as online gradient descent on a reconstruction loss), the gated delta rule (combine surgical erasure with a global forget gate), and Kimi Delta Attention (replace the scalar gate with a per-dimension one), why uniform decay alone cannot solve the memory-collision problem, and how Kimi Linear interleaves KDA with full attention to outperform pure full-attention models at 48B parameters.
Hybrid Architectures: RetNet and the Three Computation Paradigms
Building RetNet from scratch — how a single retention formula admits three computation modes (parallel for training, recurrent for inference, chunkwise for long sequences) producing identical outputs, why exponential decay and complex-exponential position encoding together fix the two failure modes of linear attention, and what the impossible triangle of training parallelism, low-cost inference, and strong performance actually requires.
Why Replace Attention? The Softmax Bottleneck and the Path to Linear Time
Why softmax is the bottleneck that every attention variant leaves untouched — and how rewriting attention as a kernel exposes an associativity trick that collapses the O(n²) cost to O(n) and turns the transformer into an RNN.
Sliding Window Attention: From Local Windows to Global Context
Borrowing from convolutions — how a sliding local window keeps attention linear in sequence length, recovers a global receptive field by stacking layers, and reaches across the whole document through a small set of task-driven global tokens.
Why Full Attention Is Wasteful: Sparse Factorization from Scratch
Most learned attention weights are near zero, so why pay for all n² token pairs? Building sparse factorized attention from scratch — strided and fixed patterns that preserve full reachability in two hops while reducing the cost from O(n²) to O(n sqrt(n)).
Why Vanilla Attention Breaks at Scale: The O(n²) Wall
A precise accounting of why standard attention becomes infeasible at long sequences: exact FLOP counts, memory costs, KV-cache growth, and the HBM bandwidth bottleneck that makes memory worse than compute.