acceptodds
Under review as a conference paper at ICLR 2027

HOLA: Hadamard Higher-Order Linear Attention

Abstract

The attention mechanism is an important reason for the success of transformers. It relies on computing pairwise relations between a query and all key tokens and applying softmax normalization. The expressiveness of softmax stems from the exponential kernel, which, however, causes quadratic computational complexity. Linear attention replaces the exponential by a single inner product of feature maps. In terms of the Taylor-series expansion of the exponential function, this amounts to a first-order approximation. Prior work has shown that the second-order term can also be computed in linear time. In this paper, we introduce Hadamard Higher-Order Linear Attention (HOLA), which extends this construction in three directions. It supports efficient factorizations of arbitrary-order terms rather than only the second-order term. The shared symmetric feature map used by prior works is replaced with distinct maps for each factor in the higher-order Hadamard product. This relaxes a low-rank constraint on the state matrix. HOLA amounts to standard linear attention at order one, includes the prior second-order construction as an exact special case, and is compatible with existing mechanisms such as gating, decay, and delta-rule updates.

Primary area:
foundation or frontier models, including LLMs
Keywords:
transformer, attention, linear attention

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_mZhfOpenReview ↗
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

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\tilde{q} = \phi(q)^{\times F}. Every existing construction repeats the same map in each factor. We show in Prop. 4.1 that factor-tying confines q~\tilde{q} to a symmetric subspace, so a state of size dϕFd_\phi^F carries a rank ceiling of only C(dϕ+F−1,F)≈dϕF/F!C(d_\phi+F−1, F) \approx d_\phi^F/F!. At F=2F=2, about half of BASED's state is redundant. Untying the factors restores dϕFd_\phi^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:

(d_φ, F)TiedUntiedFactor
(16, 2)1362561.9×
(12, 2)781441.85×
(6, 3)562163.9×
(8, 3)1205124.3×

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.

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.

Reviewer_E3WZOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes HOLA, a higher-order linear attention mechanism based on Hadamard products and asymmetric feature mappings. By relaxing the symmetry-induced rank constraint, HOLA aims to improve the expressiveness of linear attention while preserving linear complexity with respect to sequence length. Experiments on associative retrieval and video generation demonstrate promising results.

Critical strengths

S1. Interesting theoretical perspective. The paper identifies a symmetry-induced rank constraint in higher-order attention and provides a theoretical analysis motivating asymmetric feature mappings.

S2. Promising experimental results. The proposed method achieves substantial improvements on associative retrieval tasks, particularly when integrated with Gated DeltaNet.

S3. Broad applicability. The evaluation covers both autoregressive language modeling and bidirectional video diffusion, demonstrating the potential versatility of higher-order attention.

Critical weaknesses

Critical Weaknesses

W1. Limited Novelty over Existing Higher-Order Attention Methods.

The Taylor-based formulation closely resembles BASED, TaylorShift, and PolySketchFormer. The novelty of asymmetric factorization and its advantages over these methods should be more clearly established.

W2. Insufficient Theoretical Justification.

A higher rank upper bound does not necessarily imply greater effective rank or expressiveness. Moreover, the learned nonlinear feature maps do not strictly correspond to Taylor expansion terms.

W3. Unfair Comparisons between Symmetric and Asymmetric Variants.

The symmetric and asymmetric variants use different feature dimensions and model capacities, making it difficult to isolate the benefits of asymmetric factorization.

W4. Limited Computational Efficiency Analysis.

The computational cost grows exponentially with interaction order. More comprehensive evaluations of training throughput, prefill, decoding, and parallelization against optimized linear attention baselines are needed.

W5. Limited Empirical Validation of Rank Improvements.

The paper lacks direct measurements of effective rank, singular-value distributions, and attention concentration. Such analyses are important to validate the theoretical claims.

W6. Writing Quality and Organization Need Improvement.

The manuscript contains several unresolved references (e.g., “sec. ??” and “appendix ??” on Page 6), typos (e.g., “prediciotn,” “featuer,” and “modify modify”), and grammatical errors. Some appendix sections also appear incomplete or poorly organized. The paper would benefit from substantial proofreading and reorganization to improve clarity and readability.

Questions for authors

Q1. Novelty and Theoretical Justification. How does HOLA fundamentally differ from BASED and PolySketchFormer? Does relaxing the theoretical rank upper bound lead to higher effective rank and better expressiveness in practice?

Q2. Experimental Fairness and Visualization. Could the authors compare symmetric and asymmetric variants under matched feature dimensions and computational budgets, and visualize their singular-value spectra, effective ranks, and attention distributions?

Q3. Computational Efficiency and Generalization. How does HOLA perform in terms of training throughput, parallelization, prefill, and decoding efficiency compared with optimized linear attention methods? Are these advantages consistent across causal and bidirectional attention?

1 comment

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\tilde{q} = \phi(q)^{\times F}. Every existing construction repeats the same map in each factor. We show in Prop. 4.1 that factor-tying confines q~\tilde{q} to a symmetric subspace, so a state of size dϕFd_\phi^F carries a rank ceiling of only C(dϕ+F−1,F)≈dϕF/F!C(d_\phi+F−1, F) \approx d_\phi^F/F!. At F=2F=2, about half of BASED's state is redundant. Untying the factors restores dϕFd_\phi^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:

(d_φ, F)TiedUntiedFactor
(16, 2)1362561.9×
(12, 2)781441.85×
(6, 3)562163.9×
(8, 3)1205124.3×

questions by the reviewer

These are our answers to the questions of the reviewer:

Q1

Novelty

Prior methods compute the outer vector product of a vector with itself using the same map for q and k, which approximates a fixed polynomial of qᵀk. HOLA learns F distinct maps per side, so its scores are a Hadamard product of F separately learned attention matrices. Untying raises the rank ceiling from C(d_\phi+F−1, F) to d_\phi^F (136 to 256) at the same state size. The comparison table has the requested rows; one fact from it is that the prior methods store a d^2 state but only use its symmetric half.

Q2

Rank vs. effective rank

We added a new experiment answering that question.

The tied result is guaranteed. Tied rank \leq 136 holds by algebra, so measuring it shows nothing by itself. The answer is framed around two real questions: does tied actually reach 136, and does untied go beyond 136?

The new single-head experiment answers both questions (new Fig. 2). At d_\phi=16, F=2 (state 256):

  • Numerical rank: tied reaches 134–136 and untied reaches the full 256.
  • Effective rank (entropy-based): 38.6 untied vs. 16.9 tied (causal: 42.9 vs. 21.4).
  • At F=3, state 512: numerical rank 496 untied vs. 114 tied; effective rank 31.9 vs. 14.4.
  • Key-only untying (tied-q / untied-k) stays at 136, as Prop. 4.1 predicts.
  • So the higher bound does translate into higher effective rank.

Causal masking breaks the bound: A masked causal score matrix can have rank up to N, so we measure the scores before masking, as in the new experiment. The non-causal video model avoids this issue.

Relation to the Taylor series: We agree that the learned maps are not Taylor terms. Only the order structure is inspired by the series.

Experiment in Fig 2: A controlled single synthetic head (N=512, d=128, bidirectional and causal). Only the feature maps are trained, to match softmax attention.

Untied fits best at matched state: KL divergence to softmax at state 256 is 0.80 untied vs. 1.16 tied. Matching the tied model's parameters barely helps (1.12), so the gain comes from untying, not parameter count.

The exact truncated Taylor series fits worse: Taylor-2 reaches KLD 1.71 with 8,385 state entries. Even Taylor-4, with about 12.1M entries, reaches only 0.82, still worse than untied at state 512 (0.75).

Q3

Matched comparison

The new single-head experiment in Fig 2 adds a parameter-matched tied control.

Q4

Efficiency

Forward numbers: At 64K, HOLA is 11.5× faster than FA2 causal and 33.5× non-causal. At 4K causal, FA2 is faster (0.74 vs. 0.91 ms).

Decoding: O(d_\phi^F d_v) per step with a 256×64 state, 32 KB per head in bf16. This is smaller than a KV cache beyond 128 tokens.

Non-causal: The video model has no decoding phase; the cost is O(N d_\phi^F d_v).

Q5

Limited Empirical Validation of Rank Improvements

Please see our new results in Fig 2 regarding this question.

Q6

Writing Quality and Organization Need Improvement

We thank the reviewer to point this out and will improve the writing in the next update.

Reviewer_g37POpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes HOLA, a higher-order linear attention mechanism based on Hadamard products of attention scores. It uses independent feature maps to relax the rank constraints introduced by symmetric higher-order representations while retaining linear complexity in sequence length. The authors evaluate the method on long-context associative retrieval using Qwen2.5-1.5B, video generation using Wan2.1-1.3B, and kernel efficiency against FlashAttention.

Critical strengths
  1. The formulation is simple and builds naturally on existing linear attention methods. Proposition 4.1 provides a useful characterization of the rank constraint introduced by tied feature maps.

  2. Combining higher-order attention with Gated Delta Networks is interesting. The improvement in associative retrieval is substantial (Table 2), suggesting that higher-order features could be useful in recurrent attention architectures.

Critical weaknesses
  1. The main ablations are not controlled. The symmetric HLA model uses d_phi=16, while the asymmetric model uses d_phi=64 (l. 963-971), resulting in a 16x difference in state size. It is therefore unclear whether the improvements come from removing symmetry or simply increasing capacity. The same concern applies to GDN-HLA versus GDN.

  2. The experimental evidence does not sufficiently support the main claims. The proposed asymmetric third-order model is never evaluated (l. 266-267). All modified language models also have substantially worse NTP loss than the pretrained Qwen baseline (Table 2). The video comparison uses the weaker pure-linear ablation from Attention Surgery rather than its stronger hybrid configurations (Table 5). Finally, the reported 26x speedup is at d_k=16, whereas the language model uses d_phi=64, where the reported throughput is worse than FlashAttention at 16k tokens (l. 454-460).

Questions for authors
  1. Can the authors provide symmetric versus asymmetric ablations at matched feature widths and state sizes? This seems necessary to establish the main claim.

  2. Can the authors evaluate an asymmetric F=3 model? Currently the higher-order experiments do not test the proposed asymmetric formulation.

  3. Why does the original Qwen model achieve exactly 0% retrieval accuracy? A fine-tuned softmax baseline and a normalized exact-match evaluation would help clarify the results.

  4. Can the authors compare against the stronger Attention Surgery configurations at matched compute and clarify the exact configurations used for video generation?

  5. Can the authors report backward-pass and end-to-end training throughput at d_phi=64?

1 comment

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\tilde{q} = \phi(q)^{\times F}. Every existing construction repeats the same map in each factor. We show in Prop. 4.1 that factor-tying confines q~\tilde{q} to a symmetric subspace, so a state of size dϕFd_\phi^F carries a rank ceiling of only C(dϕ+F−1,F)≈dϕF/F!C(d_\phi+F−1, F) \approx d_\phi^F/F!. At F=2F=2, about half of BASED's state is redundant. Untying the factors restores dϕFd_\phi^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:

(d_φ, F)TiedUntiedFactor
(16, 2)1362561.9×
(12, 2)781441.85×
(6, 3)562163.9×
(8, 3)1205124.3×

questions by the reviewer

The following lists our answers to the questions of the reviewer:

Q1

symmetric versus asymmetric ablations at matched feature widths and state sizes?

See the answer to Q4.

Q2

Can the authors evaluate an asymmetric F=3 model?

Unfortunately, we did not have time to prepare this result.

Q3

fine-tuned softmax baseline and a normalized exact-match evaluation

With needle-in-a-haystack (NIAH), the baseline Qwwen model achieves about 80%80\% accuracy zero-shot. However, we noticed that all models training on this task immediately overfitted, so we designed the much harder task of multi-query associative recall (MQAR). These are the accuracies for the softmax-based Qwen model at 8k, 16k and 32k tokens trained under the same schedule:

Model8k16k32k
Qwen zero-shot000
Qwen trained99.799.099.4
We will add these results to the paper.

Q4

Can the authors compare against the stronger Attention Surgery configurations at matched compute

We denote Gated Delta Net (GDN) with an internal linear attention model that has a state size of 512 as GDN-512. While HLA-F2 with dϕ=64d_\phi=64 would in fact require a latent dimension of 642=409664^2=4096 we consistently had out-of-memory exceptions with a latent dimension that large, thus we used the largest latent dimension that worked. However, when we used the same training schedule, we noticed that the results were bad, So we increased the number of training steps at 32k sequence length form 4k to 8k. Symmetric or asymmetric HLA-F2 with dϕ=64d_\phi=64 is indicated by HLA-F2-sym-64 and (HLA-F2-asym-64). These two versions use the standard training schedule.

Model8k16k32k
GDN-51221.325.620.6
HLA-F2-sym0.61.20.6
HLA-F2-asym26.327.827.5

As can be seen, that GDN-512 has worse results than GDN with a much smaller state buffer.

configurations used for video generation?

Here, we use symmetric HLA with F=2F=2 factors and dϕ=16d_\phi=16 as well as F=3F=3 factors and dϕ=8d_\phi=8. Further differences stem from the different video resolutions as well as which layers use HLA. See the appendix in sec. C.1 for more details.

Q5

backward-pass at d_phi=64

Single attention layer, H100 80GB, bs=1, 12 heads, dϕ=64d_\phi=64, dv=128d_v=128.

maskNNmethodfwd (ms)bwd (ms)
causal32kHOLA31.7225.4
causal32kFA28.423.1
causal64kHOLA63.3450.5
causal64kFA232.795.4
non-causal32kHOLA17.2164.3
non-causal32kFA215.849.6
non-causal64kHOLA34.3328.3
non-causal64kFA264.8196.1

We can see from this table that the complexity of HOLA grows linearly with the sequence length whereas it doubles with the sequence length for FA2. The backward pass does not yet use fused operations (7–10× the forward cost).

end-to-end training latencies and throughput at d_phi=64

methodfwd (sec)bwd (sec)throughput (tokens/sec)
GDN, dϕ=64d_\phi=642.46.43590
GDN + HLA asym, dϕ=8d_\phi=82.59.22707
HLA asym, dϕ=8d_\phi=81.98.13180

The longer backward times for asymmetric HLA F=2 is because this kernel does not yet use fused operations.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.