- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper proposes HOLA, a higher-order linear attention mechanism built from Hadamard products of multiple separable attention kernels. The method generalizes existing second-order polynomial attention mechanisms to arbitrary interaction orders. The method represents higher-order attention scores using Hadamard products of separable kernels, allowing independent feature maps for different factors and reducing feature widths to make higher-order operations computationally practical. The authors establish a rank bound showing that sharing query maps across factors confines the lifted query representations to a symmetric tensor subspace, yielding a stricter upper bound on the rank of the attention-score matrix. Experiments on associative retrieval and video generation demonstrate improvements over several linear attention baselines, particularly when asymmetric HLA is integrated with Gated Delta Networks.
Critical strengths
- The paper addresses an important practical limitation of linear attention: maintaining strong long-range associative retrieval while reducing the quadratic computational cost of softmax attention.
- The proposed construction is conceptually simple and supports arbitrary interaction orders while retaining linear complexity in the sequence length for fixed feature dimensions. Its compatibility with existing linear-attention state updates is appealing.
- The improvement in associative retrieval obtained by combining asymmetric HLA with Gated Delta Networks is promising. The MQAR accuracy increases from 39.1% to 84.1% at 8k tokens and from 40.6% to 79.4% at 32k tokens.
Critical weaknesses
- I am not sure how novel the idea is. By the Kronecker product identity, the Hadamard product of multiple separable attention kernels is itself separable and can be represented as a single inner product in a higher-dimensional feature space. Since d is assumed to be small enough for polynomial in d to be tolerated, creating a quadratic size linear kernel might not worsen the algorithm too much. In fact any polynomial product of kernels approximating the softmax kernel can be approximated to polynomial size linear kernels (see polynomial method in Alman and Song, “Fast attention requires bounded entries”, as well as the higher-order constructions of PolySketchFormer).
- Motivation or proofs for choosing the given feature maps were not provided. It will be more interesting to see how this approximates the exponential Taylor series.
- Equation (15) computes mixture weights using the mean query representation over the complete sequence. If this is used during parallel autoregressive training, the output at an earlier position can depend on future tokens through the mixture weights. The authors should clarify whether a causal prefix-based implementation is used and how this issue is addressed.
Questions for authors
Please see weaknesses above.
3 comments
Thank you for the detailed response and clarifications. The rank analysis and the empirical improvements are interesting. While the response addresses several of my concerns, but I still view the proposed method as an incremental extension of existing higher-order linear attention approaches. I will therefore maintain my original score.
Thank you for engaging with our response and for acknowledging the rank analysis and the empirical gains.
Our main contribution is identifying a limitation of existing higher-order linear attention that, to our knowledge, has not been pointed out before: tying the feature maps across factors confines the state to its symmetric subspace and caps its rank. The fix is deliberately simple. Why it works so well is only obvious once the limitation is known. Our experiments show that this simple change yields significantly better results.
We thank the reviewer for their time and effort to read and rate this paper.
Contribution (restated)
Higher-order linear attention (BASED, TaylorShift, PolySketch) lifts features to q~=ϕ(q)×F. Every existing construction repeats the same map in each factor. We show in Prop. 4.1 that factor-tying confines q~ to a symmetric subspace, so a state of size dϕF carries a rank ceiling of only C(dϕ+F−1,F)≈dϕF/F!. At F=2, about half of BASED's state is redundant. Untying the factors restores dϕF at identical state size and essentially identical FLOPs. We claim no novelty for the Kronecker lift itself.
The following table demonstrates the effect of tied vs untied feature maps on the rank ceiling:
questions by the reviewer
These are our answers to several questions of the reviewer:
Causal leakage in the HOLA-F3 gate (Eq. 15)
The reviewer is correct about this observation. We thank the R for spotting this mistake. Unfortunately, at this point, we are unable to re-run the experiment with a fixed formulation, for instance cumsum or even a fixed gate. We also would like to point out that while this leak favors HOLA-F3 (acc 24.7 at 32k length), the variant is still inferior to untied HLA-F2 (27.5 at 32k length).
choice of feature maps
We noticed that RELU can cause extreme sparsity. In some cases, this trapped the algorithm. Empirically, softplus worked reasonably well.
Relation to the exponential Taylor series.
We agree that the lift is not novel. To relate HOLA to the series, we fit tied and untied lifts to softmax on a single synthetic head (N=512, d=128; Fig. X). Real Qwen q/k were not used in this experiment. We also compare against the exact truncated Taylor series. Untied lifts fit best at equal state. At F=3 with state 512, KLD is 0.75 untied vs. 1.23 tied (causal: 0.77 vs. 1.22). The exact Taylor-2 series fits poorly (KLD 1.71) even with 8,385 state entries, because 1+s+s²/2 grows again for s<−1. Taylor-4 needs ≈12.1M entries to reach KLD 0.82 bidirectional (0.64 causal). The learned maps are therefore not Taylor terms. Our contribution is the factor structure: tying confines the lift to the symmetric subspace, and untying lifts this rank ceiling at the same cost.
d small enough
We would like to point the reviewer to our answer to Q5 of reviewer g37P. The table contains forward times of the proposed kernel vs FlashAttention2. We can see that for every doubling of the sequence length, FA2 becomes 4 times slower whereas the latency of HLA grows linearly with the sequence length. The crossover point would be at a sequence length of 128k. Please notice that the backward kernels cannot be fairly compared since the backward kernel used in this work has not been optimized to the same degree as the forward kernel.