- Rating
- 1
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The authors study the expressivity of linear attention heads with non-negative query and key mapping weights through the lens of kernel dimension (i.e. how many dimensions does each query and key vector need to be mapped to?). They do so through the lens of the MinIP problem: given vectors find for each , . The question is what is the minimum kernel dimension required to compute this function for a set of vectors, denoted (I can't get the star to render properly, so omitting it in this review).
-
For one-head and affine output/MLP layers, the authors show while . The result extends in some sense to general heads: for heads, . That is, there is a sharp threshold: MinIP over 2 vectors is easy, but 3 vectors is hard.
-
When the output/MLP layer is allowed to instead be a -degree polynomial: in this case the authors establish a similar threshold: MinIP over vectors is easy, while vectors is hard.
-
The assumption that the MLP layer is constrained is necessary, as arbitrarily MLPs can compute MinIP with kernel dimension 1. When MLPs are more powerful, the authors obtain lower bounds on kernel dimension by restricting the communication between tokens in the attention layer.
Critical strengths
Expressivity is a well-studied and motivated problem, and kernel dimension is a reasonable metric to investigate.
Critical weaknesses
However, the authors consider a very restricted model of attention, without much motivation detailing how this choice was obtained: why linear attention? why forcing non-negative entries in the query and key mappings? This second assumption in particular seems very arbitrary and only chosen so that the proof goes through.
Similarly, why restrict the MLP to be a linear function or polynomial? We know that MLPs can for example have activations such as ReLU which is closer to what we see in practice.
Perhaps my main complaint is that the work itself is fairly unmotivated. It is observed both in theory and practice that attention can compute pairwise problems such as MinIP very well, so I'm not sure it's the right problem to choose to show some expressivity lower bounds for attention.
The paper is not very well written. While the initial definition and results are reasonably clear, any technical discussion is very terse with undefined jargon (e.g. code distance, trace-Frobenius inequality are not defined before they are applied in the technical overview). I find that the technical discussion offers very little intuition for why the claimed theorems are true (although the example in Section 3.1 was useful).
Questions for authors
see weaknesses
3 comments
I still find the motivation weak. First, the model studied of linear, non-negative kernel attention is far from the standard model of softmax attention, and the restriction of the MLP still weakens the result. I do not find the justification that arbitrary MLPs is too powerful to be convincing: for example, previous results have already established that even with unrestricted MLPs in very reasonable settings (see e.g. Sanford, Hsu, Telgarsky and Chen, Peng, Wu) large kernel dimension is required to compute some functions.
Similarly, the question of whether linear attention is as powerful as standard attention, previous work (e.g. Alman and Yu) have shown impossibility results for ANY subquadratic alternative to compute Min-IP, which already separates any linear alternative.
I do not find the presentation to be significantly improved (and in fact the rebuttal edits are not clear in the revision, which is not very helpful). I will keep my score.
Alman and Yu (2025). Their lower bounds are conditional on SETH or OVC and concern long sequences: at three tokens they do not apply. SETH has recently been reported false (OpenAI and Anthropic), and OVC remains a conjecture. Our separation is unconditional and holds at three tokens.
Sanford, Hsu and Telgarsky (2023); Chen, Peng and Wu (2024). These results rely on communication arguments, which can only bound how many bits must pass between tokens. A three-token input has just bits, so no such argument can force anything exponential there. Our rank bounds measure something these techniques cannot capture.
Thank you for your interest in our work and for your thoughtful questions and comments, we address your questions below. Our general comment provides an overview of the changes made in response to the reviews.
Question 1: Why linear attention, and why nonnegative kernels?
Kernelized linear attention uses a factored kernel to build a shared summary, making its cost linear in sequence length when feature and value widths are fixed. This can make it faster on long sequences and motivates the question (now in the revised introduction): how efficiently can this mechanism use the summary to compare candidates? Three-token Min-IP has deterministic one-way communication complexity Θ(m) (App. D), while one head with an affine readout requires exponential feature rank (Theorem 1). The difficulty we identify therefore concerns aggregating and decoding information through this mechanism, rather than information capacity alone.
Our assumption only concerns kernel evaluations: feature coordinates, values, and readout coefficients may have either sign. Nonnegative kernels ensure that the normalized attention output lies in the convex hull of the value vectors, analogous to the behavior of softmax attention. Moreover, there are several natural attention mechanisms that satisfy this assumption, including Hedgehog, ELU+1 attention (Katharopoulos et al., 2020), and FAVOR+ with fixed positive features and normalization (Choromanski et al., 2021).
Question 2: If the task of comparing all pairs of scores can be done well by dense attention, why should we care about the performance on Min-IP?
The appeal of kernelized attention is to reduce the cost from quadratic to linear in sequence length. We therefore ask whether it can solve the same tasks as dense attention and, when it needs more features or a more sensitive readout, why. Min-IP lets us examine this on a task that dense attention solves easily.
Question 3: Why not use more expressive decoders, e.g. ReLU MLPs?
We initially focused on restricted readouts because a rank-one head with sufficiently wide positional values and an unrestricted ReLU decoder can compute any function on our finite input domain. Your comments led us to revisit this construction and notice that its readout becomes increasingly sensitive as the sequence grows. This motivated our normalized-sensitivity tradeoff for general nonlinear readouts (Theorem 2) and the tight rank-one sensitivity result (Theorem 4), which we summarize in our general comment.
Question 4: Clarity and Presentation
We clarified the terminology and proof intuition, including constant-weight codes and the trace–Frobenius inequality in Section 3.1. Our general comment summarizes these changes, along with the revised abstract and results table.