Cluster B: Sub-Quadratic O(n)

The O(n²) cost of attention comes from materializing the n×n attention matrix. Linear attention approximates this using a feature map φ: softmax(QK^T) ≈ φ(Q)·φ(K)^T.

The key insight is matrix associativity: (φ(Q)·φ(K)^T)·V vs φ(Q)·(φ(K)^T·V). By computing φ(K)^T·V first — a small d×d matrix reusable for all queries — the total cost drops from O(n²·d) to O(n·d²).

The cost: softmax produces sharp, data-dependent attention weights that concentrate on a few highly relevant positions. Feature-map approximations produce softer weights — degrading quality on tasks requiring precise retrieval ('copy this exact token from position 47').

RWKV (Peng et al., 2023) is an architecture that achieves: (1) Transformer-style parallel training, (2) RNN-style O(1) memory inference. It replaces attention with a time-mixing block based on the WKV operator.

WKV is a weighted sum of past value vectors, where each past token's weight decays exponentially with distance at a learned rate w per channel. A bonus term u prevents the current token from being suppressed.

This can be computed as a prefix scan during training (parallel, log depth) or as a running recurrence during inference (O(1) memory). The same weights serve both modes — analogous to how SSMs support both convolution and recurrence.

Key difference from SSMs: RWKV's time decay is a fixed learned scalar per channel, not an input-dependent matrix.

RetNet (Sun et al., 2023) introduces a retention mechanism with three equivalent computational forms enabling the 'impossible triangle': training parallelism, O(1) inference memory, and efficient chunk-wise processing.

In parallel form, Retention(Q,K,V) = (QK^T ⊙ D)V, where D is a causal decay mask: D_nm = γ^{n-m} for n≥m (else 0). The scalar γ ∈ (0,1) is the retention rate — controlling how quickly past tokens lose influence.

Positional phases: Q and K vectors are multiplied by complex rotations e^{imθ} and e^{-inθ} respectively (similar to RoPE), so their inner product encodes relative position. Combined with exponential decay, retention is effectively linear attention + rotary phases + explicit exponential forgetting.

The recurrent form maintains a d×d state matrix that is updated with each new token — replacing the growing KV-cache with a fixed-size state.

While pure SSMs (like Mamba) solve the O(n²) memory bottleneck, they struggle with 'needle-in-a-haystack' retrieval tasks because they cannot perform exact lookups over long contexts—everything is compressed into a fixed-size state.

Hybrid architectures combine the best of both worlds. Jamba (AI21, 2024) interleaved Transformer layers with Mamba layers (e.g., a ratio of 1:7) and added MoE (Mixture of Experts). The few Attention layers maintain precise retrieval across the context window, while the Mamba layers handle local processing and sequence mixing with O(1) memory footprint.

Similarly, Griffin (DeepMind, 2024) combines local attention (windowed) with linear RNNs. By restricting attention to a local window, it bounds the KV-cache size, while the RNN aggregates global context.

Instead of abandoning attention, another path is to compute it sparsely. Full attention computes a score for every token against every other token. Sparse attention restricts this.

Local/Windowed Attention (e.g., Longformer, Mistral): Tokens only attend to a sliding window of recent tokens (e.g., the last 4096 tokens). This caps memory at O(n·w) instead of O(n²). Strided/Dilated Attention: Tokens attend to distant tokens at regular intervals (e.g., every 8th token) to capture long-range structure without full computation. Block-Sparse Attention (e.g., BigBird): A mix of local windows, random distant tokens, and a few 'global' tokens (like a [CLS] token) that attend to everything. BigBird proved this is Turing complete.