Higher-order Linear Attention

Yifan Zhang 1 Zhen Qin Quanquan Gu 2 1 Princeton University 2 University of California, Los Angeles [email protected] [email protected] · 2025

Read Higher-order Linear Attention by Yifan Zhang 1 Zhen Qin Quanquan Gu 2 1 Princeton University 2 University of California, Los Angeles [email protected] [email protected] (2025) 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-2510-27258.txt.

Introduction

Yifan Zhang, Zhen Qin, Mengdi Wang, and Quanquan Gu introduce higher-order linear attention, a cheaper way for language models to weigh context. Standard attention cost grows quadratically with sequence length, blocking long contexts. Linear-time rivals and state space models scale better but usually capture only first-order or kernel-based interactions, limiting expressiveness.

Their mechanism keeps compact running summaries, called prefix sufficient statistics, so second-order interactions are computed in linear time with constant-size state and no large pairwise matrices. Closed-form streaming identities, a strictly causal masked variant, and a chunk-parallel training scheme reproduce serial results exactly. Extensions to third and higher orders are outlined. The design offers attention-like data-dependent mixing with recurrent efficiency for long-sequence models.

Catalog record

CREATORYifan Zhang 1 Zhen Qin Quanquan Gu 2 1 Princeton University 2 University of California, Los Angeles [email protected] [email protected]
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE53 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-27258

Browse the full library · About the Tower of Babel

Full text

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

Higher-order Linear Attention Yifan Zhang 1 Zhen Qin Quanquan Gu 2 1 Princeton University 2 University of California, Los Angeles [email protected] [email protected] Abstract The quadratic cost of scaled dot-product attention is a central obstacle to scaling autoregressive language models to long contexts. Linear-time attention and State Space Models (SSMs) provide scalable alternatives but are typically restricted to first-order or kernel-based approximations, which can limit expressivity. We introduce Higher-order Linear Attention ( HLA ), a causal, streaming mechanism that realizes higher interactions via compact prefix sufficient statistics. In the second-order case, HLA maintains a constant-size state and computes per-token outputs in linear time without materializing any n × n n{\times}n matrices. We give closed-form streaming identities, a strictly causal masked variant using two additional summaries, and a chunk-parallel training scheme based on associative scans that reproduces the activations of a serial recurrence exactly. We further outline extensions to third and higher orders. Collectively, these results position HLA as a principled, scalable building block that combines attention-like, data-dependent mixing with the efficiency of modern recurrent architectures. Project Page : \url https://github.com/yifanzhang-pro/HLA 1 Introduction The Transformer architecture ( Vaswani et al. 2017 ) , powered by scaled dot-product attention, underpins modern large language models (LLMs). Yet the O(n^{2}) computational and memory complexity in sequence length n constrains long-context use. A rich line of work therefore explores more efficient attention mechanisms (e.g., Linear Attention ( Katharopoulos et al. 2020 ; Wang et al. 2020 ; Choromanski et al. 2020 ; Schlag et al. 2021 ; Sun et al. 2023 ; Qin et al. 2023 ; Yang et al. 2023 ; Qin et al. 2024 ; Yang et al. 2024b ; von Oswald et al. 2025 ) ), Modern Recurrent Neural Networks (RNNs) ( Peng et al. 2024 ; Sun et al. 2024 ; Peng et al. 2025 ) , Fast Weight Programmers (Delta Networks, Schlag et al. 2021 ), State Space Models (SSMs) ( Gu et al. 2021 ; Gu and Dao 2023 ; Dao and Gu 2024 ) and Memory Networks ( Behrouz et al. 2024 ; Behrouz et al. 2025a ; Behrouz et al. 2025b ) , which admit O(1) per-token state updates at inference. We propose Higher-order Linear Attention ( HLA ), generalizing linear attention by incorporating higher interactions through compact prefix summaries (sufficient statistics). The key observation is that higher attention-like operators admit factorized forms in terms of low-order moments (e.g., sums of key outer products), enabling exact causal streaming without constructing attention matrices. In the second-order case, HLA maintains an constant-size state per head and produces outputs in linear time per token ( O(d^{2}{+}d\,d_{v}) , here d is the query/key dimension and d_{v} the value dimension, independent to the sequence length). We address two central challenges: (i) enforcing strict autoregressive causality at second-order without sacrificing streaming updates or introducing any n{\times}n intermediates; and (ii) enabling chunk-parallel training that exactly matches the activations of a serial recurrence. First, we derive an exact masked formulation that enforces strict autoregressive causality by augmenting the state with two additional summaries; the resulting algorithm remains streaming and efficient. Second, we present a chunk-parallel training scheme based on an associative (monoid/semidirect-product) operator that yields the same activations as a serial loop while exploiting intra- and inter-chunk parallelism. Our contributions are summarized as follows: [leftmargin=*, topsep=1pt, itemsep=1pt] 1. Exact masked streaming at second order. We give a complete algebra of extended summaries that yields strictly causal second-order HLA with per-token constant cost, together with formal statements and proofs establishing masked streaming identities and online updates. The unnormalized HLA is the default operator; the ratio-normalized variant is an option built from the same summaries. 2. Associative scans that match serial activations. We define an associative (semidirect-product) operator for unmasked and masked settings (with and without exponential decay) and prove that a standard exclusive scan produces forward activations identical to those of a serial recurrence. We also state the reverse-mode algebra. 3. Third-order extension. We present the full masked third-order state and online updates, with a strictly causal streaming kernel. HLA is intended as a drop-in, attention-like mixer for long-context models. It provides (i) attention-style, data-dependent weighting; (ii) strictly causal streaming with O(1) per-token update memory independent of sequence length; and (iii) parallel training via scans without resorting to approximate backpropagation through time. We deliberately focus on algorithmic structure and implementation. 2 Background Notations. We use bold lowercase for vectors and bold uppercase for matrices/tensors. Token index t denotes the current time; d is the query/key dimension; d_{v} is the value dimension. Unless otherwise stated, HLA outputs are in the default unnormalized form, which avoids length-dependent renormalization. We adopt row-vector outputs \mathbf{o}_{t}\in\RR^{1\times d_{v}} ; a ratio-normalized (row-normalized) variant divides by a masked scalar denominator built from the same summaries for scale control and comparability with linear attention. Throughout, prefix summaries are statistics computable in streaming fashion with O(1) memory per token and per head. 2.1 Scaled dot-product attention Given queries \mathbf{Q}\in\RR^{n\times d} , keys \mathbf{K}\in\RR^{n\times d} , and values \mathbf{V}\in\RR^{n\times d_{v}} , scaled dot-product attention ( Vaswani et al. 2017 ) is \mathrm{Attn}(\mathbf{Q},\mathbf{K},\mathbf{V})=\mathrm{softmax}\!\left(\frac{\mathbf{Q}\mathbf{K}^{\top}}{\sqrt{d}}+\boldsymbol{\Lambda}\right)\mathbf{V}, where \boldsymbol{\Lambda}\in\RR^{n\times n} is the additive causal mask (zeros on and below the diagonal; -\infty above). For algebraic manipulations outside the softmax (e.g., Section 3.1 ), we use the Hadamard product \odot with a binary causal mask, denoted by \mathbf{L} (ones on and below the diagonal; zeros above), to mask bilinear forms consistently. 2.2 Linear attention Linear attentions ( Wang et al. 2020 ; Katharopoulos et al. 2020 ; Choromanski et al. 2020 ) approximate the softmax kernel by a feature map \phi:\mathbb{R}^{d}\!\to\!\mathbb{R}^{r} (maybe unnormalized): \mathrm{Attn}(\mathbf{Q},\mathbf{K},\mathbf{V})_{i}\approx\frac{\phi(\mathbf{q}_{i})^{\top}\big(\sum_{j}\phi(\mathbf{k}_{j})\mathbf{v}_{j}^{\top}\big)}{\phi(\mathbf{q}_{i})^{\top}\big(\sum_{j}\phi(\mathbf{k}_{j})\big)}. Maintaining the running sums \sum_{j}\phi(\mathbf{k}_{j})\mathbf{v}_{j}^{\top} and \sum_{j}\phi(\mathbf{k}_{j}) yields O(n\,r(d{+}d_{v})) time and O(r\,d_{v}) memory complexity. 3 Higher-order Linear Attention In this section, we will introduce Higher-order Linear Attention ( HLA ). We begin with second-order linear attention as a warm-up, and present its extension to third-order linear attention in Section 7 . Second-order tensor attention mechanism. Second-order tensor attention can be written as \mathbf{T}_{2}:=(\mathbf{Q}\mathbf{K}^{\top})(\mathbf{Q}\mathbf{K}^{\top})^{\top}=\mathbf{Q}(\mathbf{K}^{\top}\mathbf{K})\mathbf{Q}^{\top}\in\RR^{n\times n}, so that [\mathbf{T}_{2}]_{ij}=\mathbf{q}_{i}^{\top}(\mathbf{K}^{\top}\mathbf{K})\mathbf{q}_{j} . The right-hand side shows a dependence on the second moment \mathbf{K}^{\top}\mathbf{K}\in\mathbb{R}^{d\times d} , suggesting streaming implementations via prefix moments. We maintain prefix summaries at time t : \displaystyle\mathbf{S}_{t}^{K} \displaystyle\coloneqq\sum_{i\leq t}\mathbf{k}_{i}\mathbf{k}_{i}^{\top}\in\RR^{d\times d}, \displaystyle\mathbf{C}_{t}^{QV} \displaystyle\coloneqq\sum_{i\leq t}\mathbf{q}_{i}\mathbf{v}_{i}^{\top}\in\RR^{d\times d_{v}}, \displaystyle\mathbf{m}_{t}^{Q} \displaystyle\coloneqq\sum_{i\leq t}\mathbf{q}_{i}\in\RR^{d}. All the above prefix summaries can be updated in a streaming fashion. In particular, the updates of \mathbf{S}_{t}^{K} and \mathbf{C}_{t}^{QV} cost O(d^{2}) and O(d\,d_{v}) time per token, respectively. Unnormalized HLA. The output of second-order HLA at time t is the numerator-style bilinear form built from prefix moments: \mathbf{o}_{t}\;\coloneqq\;\mathbf{q}_{t}^{\top}\mathbf{S}_{t}^{K}\mathbf{C}_{t}^{QV}. (1) This choice avoids length-dependent renormalization while preserving streaming updates and the same state as the normalized variant. Normalized HLA. In order to define the normalized output of HLA, we define the numerator and denominator at t as follows: \text{num}_{t}=\mathbf{q}_{t}^{\top}\mathbf{S}_{t}^{K}\mathbf{C}_{t}^{QV},\qquad\text{den}_{t}=\mathbf{q}_{t}^{\top}\mathbf{S}_{t}^{K}\mathbf{m}_{t}^{Q}, and the normalized output of HLA is given by \mathbf{o}_{t}=\frac{\text{num}_{t}}{\text{den}_{t}+\varepsilon}=\frac{\mathbf{q}_{t}^{\top}\mathbf{S}_{t}^{K}\mathbf{C}_{t}^{QV}}{\mathbf{q}_{t}^{\top}\mathbf{S}_{t}^{K}\mathbf{m}_{t}^{Q}+\varepsilon}, (2) where \varepsilon>0 is a small constant added for numerical stability. Notably, \mathbf{S}_{t}^{K} acts as a learned, data-dependent metric on query space; \mathbf{C}_{t}^{QV} is a value accumulator modulated by past queries; and \mathbf{m}_{t}^{Q} provides a query mass for optional scale control. This mirrors a second-order polynomial kernel in (\mathbf{q},\mathbf{k}) while remaining strictly streaming and causal once masked (Section 3.1 ). Connection with linear attention. Setting

Read the complete text