RunningTensor: Generalizing Linear Attention to Higher-Order Recurrent States

• URL: http://arxiv.org/abs/2609.12814v1
• Date: Fri, 11 Sep 2026 13:07:29 GMT
• Title: RunningTensor: Generalizing Linear Attention to Higher-Order Recurrent States
• Abstract summary: RunningTensor generalizes recurrent memory to an order-$o$ tensor.<n>It retains both recurrent and parallel forms while remaining linear in sequence length $T$.<n>RunningTensor outperforms linear-attention and SSM baselines on associative recall.
• Score: 2.2153783542347805
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Linear attention and state-space models provide linear-time sequence modeling, but their recurrent memory remains a second-order tensor (a matrix), limiting the order of interactions that can be represented in the state. We introduce the RunningTensor, which generalizes this memory to an order-$o$ tensor, updated by a rank-1 outer product and read by contracting against $o-1$ vector queries. Order $2$ recovers linear attention; we study order $3$ as a proof of concept, retaining both recurrent and parallel forms while remaining linear in sequence length $T$ and improving working memory capacity from $\mathcal{O}(W^2)$ to $\mathcal{O}(W^o)$. On synthetic multi-query associative recall, RunningTensor outperforms linear-attention and SSM baselines. After pretraining, it also improves performance on language-understanding and non-synthetic retrieval tasks, suggesting that higher-order recurrent state can provide useful additional memory capacity beyond matrix-valued state.

Related papers

• Memristive-Friendly Hadamard Reservoir Computing: Structured, Multiplier-Free Recurrences at Scale [10.72107520133713]
  Reservoir Computing (RC) designs Recurrent Neural Networks around a fixed, untrained, recurrent layer, and is a natural candidate for neuromorphic hardware.<n>We replace the dense matrix with a structured orthogonal operator, built from sign diagonals, a permutation, and a fast Walsh-Hadamard transform.<n>We time the recurrent step on three hardware platforms, where it is up to $50times$ faster than a dense product and $104times$ smaller in memory.
  arXiv  Detail & Related papers  (2026-08-28T12:58:42Z)
• Fast Weight Attention for Continual Learning [75.34672054079408]
  Recurrent fast-weight memories and selective state-space models compress an expanding context into a fixed-size recurrent state.<n>We derive normalized first-order updates for squared-error regression and negative inner-product objectives.<n>We provide recurrent, masked-parallel, and chunk-parallel forms, together with numerically stable positive-decay renormalization.
  arXiv  Detail & Related papers  (2026-08-27T22:55:11Z)
• Naju: A Native Discrete State-Space Model with Independent Retention and Writing for Long-Sequence Memory [7.4750926696730895]
  Naju factorizes the recurrent update, schematically $x_n = f_nodot x_n-1 + i_nodot(B_n u_n)$, into an explicit discrete pole.<n>Naju consistently combines strong long-range memory with competitive or superior performance.
  arXiv  Detail & Related papers  (2026-07-23T07:34:07Z)
• Variational Linear Attention: Stable Associative Memory for Long-Context Transformers [0.6117371161379209]
  Linear attention reduces the quadratic cost of softmax attention to $mathcalO(T)$, but its memory state grows as $mathcalO(T)$ in Frobenius norm.<n>We introduce textbfVariational Linear Attention (VLA), which reframes the memory update as an online regularised least-squares problem.
  arXiv  Detail & Related papers  (2026-05-11T20:03:12Z)
• Higher-order Linear Attention [59.92962330635185]
  quadratic cost of scaled dot-product attention is a central obstacle to scaling autoregressive language models to long contexts.<n>We introduce Higher-order Linear Attention (HLA), a causal, streaming mechanism that realizes higher interactions via compact prefix sufficient statistics.
  arXiv  Detail & Related papers  (2025-10-31T07:54:37Z)
• Sequential-Parallel Duality in Prefix Scannable Models [68.39855814099997]
  Recent developments have given rise to various models, such as Gated Linear Attention (GLA) and Mamba.<n>This raises a natural question: can we characterize the full class of neural sequence models that support near-constant-time parallel evaluation and linear-time, constant-space sequential inference?
  arXiv  Detail & Related papers  (2025-06-12T17:32:02Z)
• Scaling Up Liquid-Resistance Liquid-Capacitance Networks for Efficient Sequence Modeling [50.994194925685434]
  LrcSSM is a $textitnon-linear$ recurrent model that processes long sequences as fast as today's linear state-space layers.<n>By forcing its Jacobian matrix to be diagonal, the full sequence can be solved in parallel.<n>LrcSSM offers a formal gradient-stability guarantee that other input-varying systems such as Liquid-S4 do not provide.
  arXiv  Detail & Related papers  (2025-05-27T20:02:59Z)
• Overcomplete Tensor Decomposition via Koszul-Young Flattenings [56.82556231289414]
  We give a new algorithm for decomposing an $n_times n times n_3$ tensor as the sum of a minimal number of rank-1 terms.<n>We show that an even more general class of degree-$d$s cannot surpass rank $Cn$ for a constant $C = C(d)$.
  arXiv  Detail & Related papers  (2024-11-21T17:41:09Z)
• TCNCA: Temporal Convolution Network with Chunked Attention for Scalable Sequence Processing [52.64837396100988]
  MEGA is a recent transformer-based architecture, which utilizes a linear recurrent operator whose parallel computation, based on the FFT, scales as $O(LlogL)$, with $L$ being the sequence length. We build upon their approach by replacing the linear recurrence with a special temporal convolutional network which permits larger receptive field size with shallower networks, and reduces the computational complexity to $O(L)$. We evaluate TCNCA on EnWik8 language modeling, long-range-arena (LRA) sequence classification, as well as a synthetic reasoning benchmark associative recall.
  arXiv  Detail & Related papers  (2023-12-09T16:12:25Z)
• Sub-Linear Memory: How to Make Performers SLiM [38.068090269482425]
  vanilla Transformers require $O(L2)$ in serial time and memory as functions of input length $L$. Recent works proposed various linear self-attention mechanisms, scaling only as $O(L)$ for serial computation. We observe a remarkable computational flexibility: forward and backward propagation can be performed with no approximations using sublinear memory.
  arXiv  Detail & Related papers  (2020-12-21T13:56:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.