acceptodds
Under review as a conference paper at ICLR 2027

Quasi Linear Kernel Attention with Infinite Capacity

Abstract

The evaluation cost of transformers with softmax attention scales quadratically with sequence length. Kernel attention addresses this by replacing softmax with a more general kernel function. In this paper, we aim to identify kernels that retain the expressivity of attention while enabling quasi linear computation. To quantify expressivity, we introduce a capacity for each kernel, measuring the maximum sequence length for which the attention matrix can approximate the identity. A higher capacity thus indicates greater expressivity. We show that expressive kernels like softmax, Gauss, and Laplace have infinite capacity. In contrast, common quasi linear kernels, such as those derived from finite dimensional feature maps, exhibit finite capacity. As a solution, we propose additive kernels constructed from univariate spline and polynomial exponential kernels. We prove that these maintain infinite capacity while allowing quasi linear computation via sorting. Finally, we implement additive sorting kernels efficiently and benchmark them against modern softmax backends, demonstrating advantages for long sequences.

Primary area:
learning theory
Keywords:
efficient attention, reproducing kernel Hilbert space, fast kernel summation, associative recall, attention capacity, transformers, long context

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_NwXQOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper focuses on the properties of kernel attention, a generalisation of softmax attention whereby the attention scores are computed as Φ(q,k)\Phi(q,k) (row-wise normalised) for a given kernel function Φ\Phi, and key/query pairs (q,k)(q,k). In particular, it aims to identify kernel definitions which are at the same time expressive and efficiently computable. Expressivity is tied to the capacity of the kernel itself, ie the largest sequence length N for which there exists queries and keys in RD\mathbb{R}^D so that the kernel-attention matrix can approximate the identity: this directly links to the recall capacity of the corresponding kernel attention layer. Efficiency is interpreted as the possibility to compute the kernel attention layer application in quasi-linear time. Several theoretical results are provided to identify capacities of various kernel families. Particular focus is given to sums of univariate kernels with piecewise-linear or Laplace profiles, as these can be computed efficiently in quasi-linear time via sorting and prefix sum. Efficient custom CUDA kernels are provided for their implementation, reporting runtime measurements matching quasi-linear complexity profiles. Performance of the analysed kernels attention variants on associative recall matches expectations from theory for the most part. The performance of these attention substitutes is measured by distilling attention layers from pertained transformers.

Critical strengths
  • The theoretical results are technically sound
  • Efficient CUDA implementations help adopting the proposed kernel attention variants
Critical weaknesses
  • The focus on capacity as a metric for expressivity is weakly motivated
Questions for authors
  • W1: why capacity?: The main reserve I have with this paper is about the use of capacity as a proxy for expressivity. In my understanding, capacity speaks more about the capability of “spreading around” q and k vectors, ie, of associating information with different directions (and indeed this measures reasonably well the performance of a layer on associative recall tasks, which relies precisely on this capability). Saying that capacity directly links to expressivity sounds to me like a logical jump. While even the term “expressivity” is used rather loosely, in general it is associated with the capacity of a layer to reproduce specific functional classes: in the case of capacity, the target function class is identity, which isn’t particularly rich. Note that choosing to focus on capacity brings about some counterintuitive conclusions: according to your theorems in Sec3.2, a uni-dimensional kernel has infinite capacity, (hence maximal “expressivity”), but you’ll have a hard time convincing anybody that deploying attention heads with dimension one is a good idea. So why should we care about capacity to begin with? It seems to me like it’s mainly useful to describe performance on recall tasks. To be fair, you do highlight this yourselves in L480, but given how capacity serves as the main motivation behind your work, it should be justified more strongly.

Minor

  • Thm1 relies on sending ∣∣q∣∣||q|| and ∣∣k∣∣||k|| to ∞\infty, but this doesn’t happen in practice, as people use QK norm: a comment on this limitation should be added.
  • Thm9 is trivial (indeed the proof is a one-liner: just repeat the q/k coordinates granted by the 1D kernel), so I would tone down the relevance of this contribution, especially in light of my comment in W1 above.
  • L480: “Theoretically, kernel attention with higher capacity can represent classes of functions that cannot be represented with lower capacity”: I strongly doubt anything can be said about this. Again, capacity only speaks about the capability to approximate identity. It doesn’t speak at all about the capability to approximate other functions, nor you show any theoretical results supporting this. Delete.
1 comment
AuthorsOpenReview ↗

Response to Reviewer NwXQ

Reviewer NwXQ

Thank you very much for your review and your comments! We first reply to W1 and then to the three specific points.

W1: Motivation of Capacity

Indeed, capacity is only one aspect of expressivity. In particular, kernels with infinite capacity can still differ in their practical performance. However, finite capacity indicates a significant limitation in expressivity. We revised the wording in several parts of the paper to make this clearer.

Beyond that, we now explain in Section 2 (and Theorem 15 in Appendix H) that the ability to approximate the identity implies that we can also approximate all permutation matrices of the same size. More generally, all patterns that assign each query uniformly to one of LL groups of keys can be approximated. Conversely, if N>Cap(Φ)N>\mathrm{Cap}(\Phi), no choice of keys and queries, and hence no training, lets attention retrieve each of NN tokens. For finite feature maps this happens at N>LN>L, which matches the associative recall experiment (Table 2).

Finally, we added an analysis of capacity for keys and queries with a prescribed norm (Appendix J), showing that larger head dimensions and faster kernel decay can improve the derived bounds (see next paragraph for details).

Bounded QK

It is correct that within a setting with QK normalization Theorem 1 is not applicable. In the revised version, we therefore added two results to analyze this setting.

First (new Appendix J), to analyze the capacity for normalized keys and queries, we define the restricted capacity Cap(Φ,ε,R)\mathrm{Cap}(\Phi,\varepsilon,R), which measures the largest sequence length for which the identity can be approximated up to an error ε\varepsilon using only keys and queries of norm exactly RR. Changing the radius RR is equivalent to changing the bandwidth of the kernel. For fixed ε\varepsilon and DD, we obtain the following asymptotic bounds (added Theorem 17, where ≈\approx denotes two-sided bounds and ≳\gtrsim denotes a lower bound, both up to constant factors):

  • For finite feature maps, Cap(Φ,ε,R)≤L\mathrm{Cap}(\Phi,\varepsilon,R)\leq L whenever ε<1/2\varepsilon<1/2.
  • For additive Laplace and additive bump, Cap(Φ,ε,R)≈R\mathrm{Cap}(\Phi,\varepsilon,R)\approx R (up to log factors).
  • For Gauss and softmax, Cap(Φ,ε,R)≳min⁡2D−1,eR2/8\mathrm{Cap}(\Phi,\varepsilon,R)\gtrsim \min\\{2^{D-1},\mathrm e^{R^2/8}\\}.
  • For Laplace, Cap(Φ,ε,R)≳min⁡2D−1,eR/2\mathrm{Cap}(\Phi,\varepsilon,R)\gtrsim \min\\{2^{D-1},\mathrm e^{R/2}\\}.

The detailed bounds of the full theorem also show that larger head dimensions DD and faster decay of C0\mathcal C_0 kernels improve the restricted capacity. In summary, our additive kernels, as well as Gauss, Laplace, and softmax, can thus achieve an arbitrarily large capacity by increasing the radius RR. For finite feature maps, the capacity remains bounded by LL. However, additive Laplace and additive bump require a larger radius RR (or equivalently a smaller bandwidth) than Gauss, Laplace, and softmax for comparable capacity.

Second, we add Corollary 4 showing that the maximal rank of the attention matrix coincides with the dimension of the RKHS. In particular, stationary C0\mathcal C_0 kernels (and additive kernels built from them) can produce full-rank attention matrices of arbitrary size. For finite feature maps, we had already shown that the rank is bounded by the number of features. We prove that these results also hold for norm-bounded keys and queries.

Thm 9

We agree that Theorem 9 is straightforward to prove. In the revised version we relabeled it as a lemma (now Lemma 11) and clarified in the text that its proof is straight-forward.

Approximated Classes (L480)

We agree that the sentence was formulated too broadly. We reformulated it to emphasize that our approximation results concern a specific class of attention patterns (the identity, permutations), and not a broad class of matrices.

Reviewer_RDUGOpenReview ↗
Rating
4
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the expressivity of a family of (quasi) linear kernel attentions. The authors propose a metric called inference capacity to measure a kernel’s expressivity. It is defined as the longest sequence length for which there exist queries and keys such that the kernel lets the attention weight matrix approximate the identity matrix. The paper analyzes a range of existing kernels and shows that softmax, Gaussian, and similar kernels have infinite capacity, whereas the kernels used in most current linear attention methods have small capacity. The authors argue that this explains why these linear attention kernels perform poorly on associative recall tasks. Based on this, they propose two kernels with sub-linear time complexity and high capacity, namely the add_bump kernel and the add_laplace kernel.

Critical strengths

The proposed theory and viewpoint in the paper is clean and not very complicated. The designs of add_bump and add_laplace are also simple, yet they resolve the capacity problem.

I found this paper is insightful for readers in gaining a better understanding of the expressivity of linear attention. The theory and perspective of this paper may inspire future work on the design of linear attention kernels.

The paper provides numerical experiments that support its theory and claims.

Critical weaknesses

In my view, capacity is effectively a binary indicator. On the finite side, its value is tied to the feature dimension L, which is essentially an existing metric. On the infinite side, kernels such as softmax, gauss, and add_bump cannot be distinguished from one another, even though their empirical performance differs noticeably. As a result, the only information capacity conveys is whether it is infinite or not, which limits its usefulness as a guide for kernel design.

Although the proposed method has quasi-linear time complexity, its speedup over full attention in the experiments is limited, which restricts its practical deployment.

In Figure 1, all the curves cluster together and the results are hard to read. I would suggest presenting them as a table instead.

Questions for authors

Why is the capacity of riesz not given in the table? Is it because it cannot be computed?

1 comment
AuthorsOpenReview ↗

Response to Reviewer RDUG

Many thanks for the review and the comments! We respond to your comments point by point.

Binary Indicator

We agree that the main role of capacity is to distinguish kernels with finite capacity from those with infinite capacity.

For kernels with finite feature maps, capacity can be smaller than the number of independent features LL. For instance, the kernel Φ(x,y)=φ(x)Tφ(y)\Phi(x,y)=\varphi(x)^T\varphi(y) with φ(x)=[1,f(x)]T\varphi(x)=[1,f(x)]^T for nonconstant f ⁣:RD→[0,1]f\colon\mathbb{R}^D\to[0,1] has L=2L=2 independent features. Since Φ(x,y)∈[1,2]\Phi(x,y)\in[1,2] for all x,y∈RDx,y\in\mathbb{R}^D, every entry of the attention matrix is at least 1/(2N)1/(2N) after normalization. Thus, the identity cannot be approximated arbitrarily well for any N≥2N\geq2, so Cap(Φ)=1\mathrm{Cap}(\Phi)=1. This shows that the upper bound LL can be strict. We added this example to the revised version (Appendix C).

For kernels with infinite capacity, we added an analysis of the "restricted" capacity for keys and queries with a prescribed norm RR (Appendix J). We show that our additive kernels, as well as Gauss, Laplace, and softmax, can achieve arbitrarily large restricted capacity as RR increases. However, the restricted capacity of Gauss, Laplace and softmax grows faster than for the additive kernels. Thus, the restricted capacity gives a finer comparison among these kernels.

Speedup

While we agree that the compared backends for softmax attention are faster for short sequences, one can clearly see the advantages of quasi-linear attention for long sequences. Indeed, for N=131072N=131072, it is about 31×31\times faster than MEM_EFF32 and 5×5\times faster than FlashAttention, even though these backends are heavily optimized and FlashAttention uses fp16 instead of fp32.

Fig 1

Thanks for the suggestion. We follow it and replaced the figure by Table 2.

Capacity of the Riesz kernel

We did not report the capacity of the Riesz kernel in the original version because it was unclear to us. In the revised version, we prove that it is infinite for D≥2D\geq 2 (Proposition 9) and update Table 1 accordingly. However, approximating the identity requires keys and queries whose norms span many orders of magnitude, which is infeasible in floating-point arithmetic. This is why riesz still fails in the associative recall experiment.

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

This paper studies the trade-off between expressivity and computational efficiency in kernel attention. The authors introduce a notion of kernel capacity, defined as the maximum sequence length for which the corresponding attention matrix can approximate the identity matrix arbitrarily well.

Using this definition, the paper shows that several common kernels, including softmax, Gaussian, and Laplace kernels, have infinite capacity, whereas kernels based on finite-dimensional feature maps have capacity bounded by their feature dimension.

To achieve efficient attention without sacrificing infinite capacity, the authors propose additive kernels constructed from univariate Laplace and spline functions. By exploiting sorting-based algorithms for one-dimensional kernel summation, the resulting attention can be computed exactly in quasi-linear time for fixed feature dimensions.

The authors evaluate their approach through associative-recall experiments, CUDA runtime benchmarks, and downstream tasks involving text embeddings and image classification. The results show promising efficiency improvements at long sequence lengths, although the proposed additive kernels generally exhibit some performance degradation compared with standard softmax attention.

Critical strengths

Strength 1: An interesting theoretical perspective on kernel-attention expressivity.

The paper introduces a clear mathematical definition of attention capacity and connects it to the dimension of the corresponding reproducing kernel Hilbert space (RKHS).

I find the distinction between finite-capacity feature-map kernels and infinite-capacity kernels useful. It provides another way to understand the representational limitations of conventional linear attention, particularly when the attention kernel is approximated using a fixed-dimensional feature map.

The proposed additive kernels are also a meaningful contribution. By combining univariate infinite-capacity kernels with efficient sorting-based summation, the authors obtain a construction that avoids explicitly forming the quadratic attention matrix while retaining infinite capacity under their definition.

I appreciate that the method provides an exact algorithm for the chosen kernels, rather than relying on a finite-dimensional approximation to softmax attention.

Strength 2: Concrete algorithmic development and promising long-sequence efficiency.

The paper goes beyond the theoretical construction by developing sorting-based CUDA implementations and comparing them against optimized softmax attention backends.

The runtime results are encouraging, particularly at longer sequence lengths where the proposed algorithms begin to show meaningful computational advantages.

I also appreciate the inclusion of associative-recall, text embedding, and image classification experiments. These evaluations help examine whether the theoretical properties translate into useful attention behavior.

Although the additive kernels do not consistently match softmax performance, the results suggest that the proposed method may offer a useful trade-off between computational cost and predictive quality in long-sequence settings.

Critical weaknesses

Weakness 1: Infinite capacity does not necessarily imply strong practical expressivity.

My main theoretical concern is the practical interpretation of the proposed capacity measure.

The definition considers whether there exist query and key representations that make the attention matrix arbitrarily close to the identity. However, it does not impose constraints on the magnitudes or pairwise distances of these representations.

For stationary kernels such as the Laplace kernel, infinite capacity can be obtained by placing token representations sufficiently far apart. As the pairwise distances increase, the off-diagonal kernel values approach zero, allowing the attention matrix to approximate the identity.

While this construction is mathematically valid, I am not convinced that it fully captures the expressivity requirements of practical Transformers. In realistic settings, query and key magnitudes, kernel bandwidths, and numerical precision are constrained. The ability to approximate identity attention using arbitrarily separated representations may therefore be less informative than it initially appears.

I am also concerned that identity approximation captures only one aspect of attention expressivity.

The proposed additive kernels compute similarities through independent coordinate-wise terms. This structure can be computationally advantageous, but it may restrict the interactions that the kernel can represent across feature dimensions.

Consequently, having infinite capacity under the proposed definition does not necessarily mean that an additive kernel can represent general high-dimensional attention patterns as effectively as softmax.

The downstream results seem consistent with this concern. For example, additive Laplace achieves 62.12 on MTEB, compared with 64.41 for the softmax teacher. On LoCo at 8192 tokens, the reported scores are 0.858 and 0.883, respectively.

These gaps suggest that the proposed capacity measure alone may not be sufficient to predict practical attention quality. I would find the theoretical contribution more convincing if the authors also considered capacity under bounded representations or discussed which additional kernel properties are important for downstream performance.

Weakness 2: The practical implementation and training-time efficiency evaluation are incomplete.

My second concern is the gap between the theoretical computational complexity and the current implementation.

The paper establishes quasi-linear algorithms for the proposed additive kernels and reports promising forward-pass runtime results. However, the custom CUDA implementation of additive Laplace is described as forward-only, while causal attention is discussed at the algorithmic level but has not been implemented.

This makes it difficult to assess the practical efficiency of the method in a complete Transformer training pipeline.

In particular, sorting-based kernel summation introduces implementation requirements that may affect backward-pass performance and memory consumption. Without corresponding backward kernels or end-to-end training benchmarks, it is unclear whether the forward-pass advantages translate into comparable training-time improvements.

I would also like to understand how gradients were computed during the reported distillation experiments, given the forward-only status of the custom additive Laplace implementation.

Another limitation is that the additive kernels still show noticeable performance degradation compared with softmax on some downstream tasks, even when substantial teacher distillation is used.

I understand that matching softmax performance may not be the primary objective of this work, given its theoretical focus. However, the quality gap and incomplete training implementation make it difficult to assess how broadly the proposed kernels could be used as practical replacements for standard attention.

A more complete comparison covering forward and backward computation, peak memory usage, and end-to-end training throughput would strengthen the practical contribution.

Questions for authors

Q1. Practical interpretation of infinite capacity

Could the authors investigate how the proposed capacity measure changes when query and key norms are bounded?

For example, how large must the feature magnitudes or pairwise distances become as the sequence length increases to approximate the identity matrix within a fixed error tolerance?

I would also be interested in an analysis under fixed kernel bandwidth and bounded feature representations. This could help clarify how closely the proposed notion of infinite capacity relates to the conditions encountered in practical Transformer models.

Q2. End-to-end training efficiency and implementation completeness

The paper mentions that the custom additive Laplace CUDA implementation currently supports only the forward pass. How were gradients computed for this kernel during the reported distillation experiments?

Could the authors provide end-to-end training throughput, peak memory usage, and backward-pass runtime comparisons against FlashAttention under comparable numerical precision?

I would also appreciate clarification on whether the proposed sorting-based backward algorithms are expected to retain the same practical efficiency advantages as the forward implementation.

Q3. Relationship between theoretical capacity and downstream performance

Despite having infinite capacity under the proposed definition, additive Laplace and additive bump kernels underperform softmax and the non-additive Laplace kernel on several downstream metrics.

Could the authors provide further analysis of the representational limitations introduced by coordinate-wise additivity?

In particular, I would be interested in understanding which properties beyond identity-approximation capacity are most relevant to practical attention quality. An experiment that separates the effects of kernel capacity from those of additive structure could help explain the observed performance differences.

1 comment
AuthorsOpenReview ↗

Response to Reviewer vAnq

Thank you very much for the detailed review. We reply to your comments point by point.

Bounded Keys and Queries (Q1 + W1)

Thank you for this comment. We added two results to analyze the setting of bounded or normalized keys and queries.

First, we added a capacity analysis for normalized keys and queries (added Appendix J). To this end, we define the restricted capacity Cap(Φ,ε,R)\mathrm{Cap}(\Phi,\varepsilon,R), which measures the largest sequence length for which the identity can be approximated up to an error ε\varepsilon using only keys and queries of norm exactly RR. Changing the radius RR is equivalent to changing the bandwidth of the kernel. For fixed ε\varepsilon and DD, we obtain the following asymptotic bounds (added Theorem 17, where ≈\approx denotes two-sided bounds and ≳\gtrsim denotes a lower bound, both up to constant factors):

  • For finite feature maps, Cap(Φ,ε,R)≤L\mathrm{Cap}(\Phi,\varepsilon,R)\leq L whenever ε<1/2\varepsilon<1/2.
  • For additive Laplace and additive bump, Cap(Φ,ε,R)≈R\mathrm{Cap}(\Phi,\varepsilon,R)\approx R (up to log factors).
  • For Gauss and softmax, Cap(Φ,ε,R)≳min⁡2D−1,eR2/8\mathrm{Cap}(\Phi,\varepsilon,R)\gtrsim \min\\{2^{D-1},\mathrm e^{R^2/8}\\}.
  • For Laplace, Cap(Φ,ε,R)≳min⁡2D−1,eR/2\mathrm{Cap}(\Phi,\varepsilon,R)\gtrsim \min\\{2^{D-1},\mathrm e^{R/2}\\}

Our additive kernels, as well as Gauss, Laplace, and softmax, can thus achieve an arbitrarily large capacity by increasing the radius RR. For finite feature maps, the capacity remains bounded by LL. However, additive Laplace and additive bump require a larger radius RR (or equivalently a smaller bandwidth) than Gauss, Laplace, and softmax.

Second, we show (added Corollary 4) that the maximal rank of the attention matrix coincides with the dimension of the RKHS. In particular, stationary C0\mathcal C_0 kernels (and additive kernels built from them) can produce full-rank attention matrices of arbitrary size. For finite feature maps, we had already shown that the rank is bounded by the number of features. We prove that these results also hold for norm-bounded keys and queries.

Backward Pass, Training and Additional Benchmarks (Q2 + W2)

In the revised version, we extended the numerical evaluation as requested. We added a backward pass to the additive Laplace CUDA backend, so both additive kernels now support gradients. Their runtimes and break-even points are similar. We report the backward-pass timings (Table 7, Appendix E.2) and peak memory usage (Table 4). For the additive Laplace and additive Riesz kernels, peak memory usage is about 2−3×2-3\times the memory required to store the input and output sequences.

For distillation of the text-embedding transformers, we truncate sequences to 512 tokens. At this sequence length, the speed advantage of the quasi-linear implementation is negligible, so we used the plain KeOps implementation. In particular, we used the custom CUDA backends only for inference on LoCo.

Downstream Performance (Q3 + W1)

We agree that capacity is only one aspect of expressivity. Finite capacity is a provable limitation, and kernels with infinite capacity can still differ in downstream performance. In particular, there are two noticible structural limitations of additive kernels, which we now include in the paper.

  • The RKHS of an additive kernel is HΦ=∑d=1Dfd(xd):fd∈Hϕ\mathcal H_\Phi=\\{\sum_{d=1}^D f_d(x_d):f_d\in\mathcal H_\phi\\}. This space can be infinite-dimensional, but its elements are sums of univariate functions. Since the RKHS describes the function space generated by kernel sums, this structure limits the interactions between coordinates (see the new Appendix B).
  • As outlined in the first part of our reply, the lower bounds on restricted capacity grow more slowly with RR for the additive kernels in the regime where the bounds for Gauss, Laplace, and softmax grow exponentially.

Beyond capacity, our LoCo results suggest that stationarity helps with extrapolation to longer sequences. The nonstationary feature-map kernels degrade substantially on LoCo. Note that in this context we show in Proposition 6 (numbering from the revised version) that the only FFMs fulfilling this are finite sums of cosines. For the numerical stability it is also advantagous if the kernel is non-negativ (or better positive), to avoid zero-divisions in the definition of attention (which is false for finite sums of cosines if ωl≠0\omega_l\neq 0).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.