- 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 (row-wise normalised) for a given kernel function , and key/query pairs . 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 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 and to , 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.
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 L groups of keys can be approximated. Conversely, if N>Cap(Φ), no choice of keys and queries, and hence no training, lets attention retrieve each of N tokens. For finite feature maps this happens at N>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), which measures the largest sequence length for which the identity can be approximated up to an error ε using only keys and queries of norm exactly R. Changing the radius R is equivalent to changing the bandwidth of the kernel. For fixed ε and D, we obtain the following asymptotic bounds (added Theorem 17, where ≈ denotes two-sided bounds and ≳ denotes a lower bound, both up to constant factors):
The detailed bounds of the full theorem also show that larger head dimensions D and faster decay of C0 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 R. For finite feature maps, the capacity remains bounded by L. However, additive Laplace and additive bump require a larger radius R (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 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.