Variational Linear Attention: Stable Associative Memory for Long-Context Transformers

Vishal Pandey, Gopal Singh · 2026

Read Variational Linear Attention: Stable Associative Memory for Long-Context Transformers by Vishal Pandey, Gopal Singh (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-11196.txt.

Introduction

Vishal Pandey and Gopal Singh introduce Variational Linear Attention, or VLA, a stable associative memory for long-context transformers. Linear attention cuts softmax attention from quadratic to linear time, but its memory state grows in Frobenius norm, interfering with stored associations.

VLA reframes the memory update as online regularised least-squares with an adaptive penalty matrix kept by the Sherman-Morrison formula. Scaling the write direction to unit length sets the recurrence Jacobian spectral norm to one. This holds for all lengths and head sizes, and the state norm stays bounded under bounded inputs. VLA cuts the state Frobenius norm 109-fold versus standard linear attention at length 1000. VLA keeps near-perfect accuracy on multi-query associative recall in the per-head regime, holding 62 percent accuracy at the capacity boundary. A Triton kernel runs 14 times faster than Python, beating softmax latency near 43,000 tokens. Builders get bounded-memory linear attention.

Catalog record

CREATORVishal Pandey, Gopal Singh
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE60663
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.11196

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Variational Linear Attention: Stable Associative Memory for Long-Context Transformers Vishal Pandey, Gopal Singh Abstract Linear attention reduces the quadratic cost of softmax attention to 𝒪 ⁡ ( T ) \mathcal{O}(T) , but its memory state grows as 𝒪 ⁡ ( T ) \mathcal{O}(T) in Frobenius norm, causing progressive interference between stored associations. We introduce Variational Linear Attention (VLA), which reframes the memory update as an online regularised least-squares problem with an adaptive penalty matrix maintained via the Sherman-Morrison rank-1 formula. We prove that normalising the write direction to unit length gives the recurrence Jacobian spectral norm exactly 1 1 for all sequence lengths and head dimensions (Proposition 2), and that the state norm is self-limiting under bounded inputs (Proposition 1). Empirically, VLA reduces ‖ S t ‖ F \|S_{t}\|_{F} by 109 × 109\times relative to standard linear attention at T = 1,000 T{=}1{,}000 , achieves near-perfect exact-match accuracy on multi-query associative recall within the effective per-head memory regime ( n pairs < d h n_{\text{pairs}}<d_{h} ), maintaining substantially higher retrieval performance than DeltaNet and standard linear attention under increasing memory load, and maintains 62% accuracy at the per-head capacity boundary. A Triton-fused kernel achieves 14 × 14\times speedup over sequential Python and 𝒪 ⁡ ( T ) \mathcal{O}(T) scaling, crossing below softmax attention latency at approximately 43 000 tokens. K eywords linear attention \cdot associative memory \cdot Sherman-Morrison update \cdot fast-weight programmers \cdot long-context transformers \cdot recursive least squares \cdot sequence modeling 1 Introduction Long-context sequence modeling has emerged as a central challenge in natural language processing, yet the dominant solutions remain unsatisfying at scale. Transformer attention [ 10 ] requires O(T^{2}) time and O(Td) memory, making deployment over sequences of 10^{5} tokens prohibitively expensive. Linear attention [ 6 ] removes the quadratic bottleneck but introduces a different failure mode: the internal memory state grows without bound, producing a Frobenius norm that scales as O(T) and degrades associative retrieval accuracy at long range. We argue that this is not a computational problem but a memory stability problem, and we address it directly. 1.1 Why linear attention fails as associative memory Linear attention maintains a running state S_{t}=S_{t-1}+v_{t}k_{t}^{\top} . This update is unconditional: every new key-value pair is accumulated with equal weight regardless of what S already stores. Over a sequence of T tokens, \mathbb{E}[\|S_{T}\|_{F}]=O(T) for random inputs, we verify empirically that \|S_{T}\|_{F} reaches 1 600 at T=1{,}000 while our method stays below 15 (Figure 2 b). This unbounded growth causes stored associations to interfere with one another, degrading retrieval as context length increases. DeltaNet [ 11 ] partially alleviates this with a gated update S_{t}=\beta_{t}S_{t-1}+(v_{t}-S_{t-1}k_{t})k_{t}^{\top} , where a learned scalar gate \beta_{t}\in(0,1) decays the full state uniformly. The scalar gate limits capacity: it forgets all directions at once rather than selectively retiring only the directions most recently overwritten. This distinction matters under high memory load; we show that DeltaNet degrades to near-random accuracy at n_{\text{pairs}}=24 while our method retains near-perfect recall (Figure 2 c). 1.2 Variational memory geometry We propose Variational Linear Attention (VLA), which reformulates the memory update as an online regularised least-squares problem with an adaptive penalty matrix M_{t} . Minimising the resulting objective yields the update: S_{t}=S_{t-1}+(v_{t}-S_{t-1}\hat{k}_{t})\,\hat{\alpha}_{t}^{\top},\quad\hat{\alpha}_{t}=A_{t}\hat{k}_{t}\,/\,\|A_{t}\hat{k}_{t}\|, (1) where A_{t}=M_{t}^{-1} is maintained exactly using the Sherman-Morrison rank-1 formula at O(d^{2}) cost per step. Intuitively, A_{t} accumulates outer products of penalty directions u_{t}u_{t}^{\top} , so subspaces that were recently written receive smaller updates, a matrix-valued analogue of DeltaNet’s scalar gate. This per-direction selectivity is the mechanism that preserves old associations while integrating new ones. The formulation connects linear attention with classical Recursive Least Squares (RLS) adaptive filters [ 5 ] , providing both a principled derivation and a stability theory absent from prior fast-weight approaches. 1.3 Contributions • Architecture. We introduce VLA, which replaces linear attention’s unconditional accumulation with a residual-error update governed by a d{\times}d adaptive penalty inverse A_{t} , maintained via Sherman-Morrison updates (§ 3 ). • Theory. We prove two stability results (§ 4 ): (1) \|S_{T}\|_{F} is self-limiting under bounded inputs ( Proposition 1 ); and (2) the recurrence Jacobian \partial S_{t}/\partial S_{t-1}=I-\hat{\alpha}_{t}\hat{k}_{t}^{\top} has spectral norm exactly 1 for all t , guaranteeing stable gradient flow at arbitrary depth ( Proposition 2 ). • Efficiency. We derive a parallel Blelloch-scan formulation and a fused Triton kernel that achieves 14 \times speedup over sequential Python and O(T) scaling, crossing below softmax attention latency at approximately 43 000 tokens (§ 6 ). • Empirical results. On multi-query associative recall (MQAR), VLA maintains near-perfect accuracy at n_{\text{pairs}}=24 ( <\!d_{h}=32 per-head capacity) while DeltaNet collapses to 0.010 and standard linear attention to 0.074. The state norm is 100 \times lower than linear attention at T=1{,}000 , confirming the stability theory empirically (§ 6 ). Together, these results demonstrate that controlling the geometry of the memory update, rather than only its computational cost, is essential for reliable long-context performance. 2 Background 2.1 Transformer attention as associative memory Given a sequence \{x_{t}\}_{t=1}^{T} , attention computes queries, keys, and values via learned projections q_{t}=W_{q}x_{t} , k_{t}=W_{k}x_{t} , v_{t}=W_{v}x_{t} , and produces: o_{t}=\sum_{s\leq t}\frac{\exp(q_{t}^{\top}k_{s}/\sqrt{d})}{\sum_{r\leq t}\exp(q_{t}^{\top}k_{r}/\sqrt{d})}\,v_{s}. (2) This is content-addressable retrieval: values v_{s} are recalled in proportion to how closely their keys k_{s} match the current query [ 7 ] . Exact computation requires \mathcal{O}(T^{2}) operations, making it infeasible at the sequence lengths that motivate this work. 2.2 Linear attention and kernel feature maps 6 replace the softmax kernel with a positive feature map \phi satisfying \exp(q^{\top}k)\approx\phi(q)^{\top}\phi(k) , enabling the output to be written as a ratio of two recurrences: S_{t}=S_{t-1}+\phi(k_{t})v_{t}^{\top},\qquad z_{t}=z_{t-1}+\phi(k_{t}),\qquad o_{t}=\frac{S_{t}\,\phi(q_{t})}{\phi(q_{t})^{\top}z_{t}}. (3) This reduces complexity to \mathcal{O}(Td^{2}) with O(d^{2}) state. The limitation is the additive update: every token writes to S_{t} with equal weight regardless of what is already stored. Formally, \mathbb{E}[\|S_{T}\|_{F}]=\mathcal{O}(T) for random inputs, causing interference between stored associations to grow unboundedly with sequence length. We demonstrate this empirically in Section 6 . Multiple feature maps have been proposed, including random Fourier features [ 3 ] and ELU+1 [ 6 ] . VLA is compatible with any positive feature map; we use ELU+1 throughout. 2.3 DeltaNet and fast-weight programmers 9 showed that recurrent networks can learn to program a separate fast-weight memory matrix. 8 later demonstrated that linear transformers are a special case of this framework. DeltaNet [ 11 ] makes the connection explicit with an error-corrective update: S_{t}=\beta_{t}S_{t-1}+\bigl(v_{t}-S_{t-1}k_{t}\bigr)k_{t}^{\top}, (4) where \beta_{t}\in(0,1) is a per-step scalar gate that decays the existing state. Correcting the prediction error v_{t}-S_{t-1}k_{t} reduces interference relative to pure accumulation, and the scalar gate provides soft forgetting. The key limitation of the scalar gate is that it scales all directions of S_{t} equally: it cannot preferentially forget directions that were recently overwritten while preserving directions that store older, stable associations. VLA replaces the scalar gate with a d{\times}d matrix A_{t} , enabling direction-selective memory updates (§ 3 ). 2.4 Recursive least squares Recursive Least Squares [ 5 ] maintains an estimate S_{t} that minimises the accumulated squared prediction error: S_{t}=\operatorname*{arg\,min}_{S}\sum_{s=1}^{t}\|v_{s}-Sk_{s}\|^{2}+\operatorname{tr}(SM_{t}S^{\top}). (5) The optimal update uses the Sherman-Morrison formula to maintain the inverse covariance A_{t}=M_{t}^{-1} exactly: A_{t}=A_{t-1}-\frac{A_{t-1}u_{t}u_{t}^{\top}A_{t-1}}{1+u_{t}^{\top}A_{t-1}u_{t}},\qquad S_{t}=S_{t-1}+\bigl(v_{t}-S_{t-1}k_{t}\bigr)(A_{t}k_{t})^{\top}, (6) at \mathcal{O}(d^{2}) per step with no matrix inversion. The inverse covariance A_{t} contracts in directions that have accumulated large penalty, automatically regulating which subspaces receive large updates. In §

Read the complete text