How Linear Attention Learns “Write‑Before‑Think”: Parallel Multi‑Step Memory Writes with PRISM

Background

Transformer attention stores a full KV cache for every token, giving it an "unlimited backpack" but causing O(N²) memory and compute growth with sequence length N. Linear‑attention models replace this with a fixed‑size state matrix S (the "finite backpack"), achieving O(N) complexity because S’s size does not grow with N. However, existing linear‑attention models (e.g., Gated DeltaNet, RWKV, Mamba) update S with a single rank‑1 outer‑product per token, limiting expressive power. Test‑Time Training (TTT‑MLP) upgrades the state to an MLP weight matrix and performs multi‑step gradient descent (GD) on each token, yielding much higher quality but introducing serial dependencies that prevent parallel scan and cause severe throughput loss (≈174× slower than GDN).

Analysis of TTT‑MLP

TTT‑MLP’s state consists of two weight matrices (W₁, W₂). Expanding the gradient of W₂ reveals a recurring update pattern:

Step size – the activation of each hidden unit, controlling write intensity.

Residual – the portion of the state not yet written, which decays across steps.

Direction – the learned direction of each write, differing at every step because the weight matrix changes.

This "step‑size × residual × direction" pattern provides both depth (through residual decay) and width (multiple directions from W₁), explaining TTT‑MLP’s superior expressivity. The same weight‑per‑step updates also create two serial bottlenecks:

Inter‑token seriality : the update couples forgetting and writing, breaking the history‑independent assumption required for parallel scan.

Intra‑step seriality : each GD step depends on the previous step’s weight, forcing a sequential loop.

PRISM Design

PRISM (Parallel Residual Iterative Sequence Model) reconstructs the step‑size × residual × direction pattern on a linear‑attention state that remains compatible with parallel scan, eliminating both token‑wise and step‑wise seriality.

Core Iteration

For L steps, PRISM performs the update

Each step adds a rank‑L contribution; the first step reduces to the standard linear‑attention write, and subsequent steps add low‑rank corrections with less than 10 % extra parameters.

Token‑wise Parallelism

PRISM separates write and erase (mirroring Gated DeltaNet), making each iteration a pure function of the current input. This allows reuse of the parallel‑scan kernel from Mamba, preserving the associative binary operation needed for parallel prefix computation.

Local Anchor Proxy

A short‑convolution (ShortConv) computes a local history vector (the "anchor") that replaces the global state S. Because the anchor depends only on a bounded window of recent tokens, every token’s computation is independent and can run concurrently.

Step‑wise Parallelism

The anchor provides pre‑computed statistics, decoupling the direction chain. PRISM absorbs the GELU non‑linearity into a pre‑conditioner, turning the multi‑step GD recurrence into an element‑wise linear recurrence that can be expressed as a single fused kernel. The closed‑form computation is

Thus the L‑step loop collapses into one kernel, requiring a single HBM→SRAM transfer.

Experiments

Sequence Recommendation

On four public recommendation benchmarks (including Amazon), PRISM matches Transformer quality, outperforms most linear‑attention baselines, and runs 174× faster than TTT‑MLP while using comparable compute.

Large‑scale Language Modeling

Training on SlimPajama (2 B tokens) with a 130 M‑parameter model, PRISM achieves the best perplexity on WikiText, the lowest LAMBADA perplexity, and the highest average accuracy across nine zero‑shot downstream tasks, beating GDN by 3.2 percentage points .

Ablation Studies

Setting L = 1 (single‑step solver) yields almost identical training perplexity but drops downstream accuracy by 2.9 pp , indicating that rank‑L writes benefit long‑range retrieval rather than next‑token prediction.

Sharing the key matrix across steps degrades performance, confirming that each step needs its own direction space.

Extended Discussion

Even with rank‑L writes, the finite backpack S has limited capacity (size ≈ |S|). When sequences reach hundreds of thousands of tokens, important information may be overwritten. PRISM’s local anchor approximates the global state with a short‑range convolution; the approximation degrades for dependencies spanning thousands of steps. Inserting occasional Transformer layers restores a global, non‑linear state, effectively “upgrading” the short‑conv anchor to full attention. This explains the recent success of hybrid architectures (e.g., Jamba, Zamba, Griffin) that combine linear‑attention/SSM layers with Transformers.

PRISM’s architecture—standard linear‑attention write plus a low‑rank side‑path—mirrors LoRA (Low‑Rank Adaptation). This suggests a parameter‑efficient fine‑tuning scheme for linear‑attention models: freeze the base iteration and add a PRISM‑style low‑rank residual branch, which incurs negligible extra compute because the first step already matches the original write.

Conclusion

PRISM demonstrates that a "write‑before‑think" paradigm is feasible for linear‑attention models. By explicitly rebuilding the step‑size × residual × direction pattern, using a local anchor proxy to remove token‑wise dependencies, and applying closed‑form pre‑computation to eliminate step‑wise loops, PRISM attains multi‑step expressive power with minimal parameter overhead and training speed comparable to GDN. Future work will explore scaling PRISM to larger models, its impact on recommendation systems, and its use as a LoRA‑style fine‑tuning method.

References: Sun et al., NeurIPS 2024; Yang et al., NeurIPS 2024; Katharopoulos et al., ICML 2020.

Code example

[1] Sun et al. “Learning to (Learn at Test Time): RNNs with Expressive Hidden States.” NeurIPS 2024.
[2] Yang et al. “Gated Delta Networks with Pairwise Tokenized Graphs.” NeurIPS 2024.
[3] Katharopoulos et al. “Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention.” ICML 2020.