acceptodds
Under review as a conference paper at ICLR 2027

Three Tokens Force Exponential Feature Rank in Nonnegative Kernel Attention

Abstract

How much feature rank does comparison require in kernel attention? On Min-IP over -bit tokens, rank one solves every sequence of length at most two exactly. At length three, the minimum feature rank of one normalized nonnegative kernel-attention head is for error strictly below on every input, even with arbitrary finite-dimensional tokenwise values and query-dependent affine readouts. Dense softmax solves this three-token task with -dimensional scores and temperature constant in . For every fixed number of heads , the minimum total feature rank is for the same error guarantee at exact length in one attention layer with affine mixing. These bounds also hold with position-dependent maps and a final causal query. For one head with polynomial readout of fixed degree at most , rank one suffices at exact length , while exact length requires exponential feature rank. With unrestricted exact-real decoding, a scalar rank-one construction solves the task at every finite length. This motivates a separate bound on total communication for deterministic models with finite-alphabet cross-token channels and any number of heads and layers. In this setting, correctness up to length requires bits over a range of lengths that grows exponentially with .

Primary area:
learning theory
Keywords:
linear attention, kernel attention, attention expressivity, feature rank, lower bounds, Min-IP, transformers

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_9nqgOpenReview ↗
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 x1,…,xn∈{0,1}mx_1, \dots, x_n \in \{0, 1\}^{m} find for each ii, min⁡⟨xi,xj⟩\min \langle x_i, x_j \rangle. The question is what is the minimum kernel dimension required to compute this function for a set of nn vectors, denoted r(n,m)r(n, m) (I can't get the star to render properly, so omitting it in this review).

  1. For one-head and affine output/MLP layers, the authors show r(2,m)=1r(2, m) = 1 while r(3,m)=2Ω(m)r(3, m) = 2^{\Omega(m)}. The result extends in some sense to general heads: for HH heads, r(H+1,m)=2ΩH(m)r(H + 1, m) = 2^{\Omega_H(m)}. That is, there is a sharp threshold: MinIP over 2 vectors is easy, but 3 vectors is hard.

  2. When the output/MLP layer is allowed to instead be a DD-degree polynomial: in this case the authors establish a similar threshold: MinIP over ≤D+1\leq D + 1 vectors is easy, while D+2D + 2 vectors is hard.

  3. 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

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)\Theta(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.

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 3m3m bits, so no such argument can force anything exponential there. Our rank bounds measure something these techniques cannot capture.

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

This paper studies the representational power of linear attention for the specific task of "minimum inner product." Given a sequence of tokens corresponding to length-mm binary strings, and given the index for one such token, the goal is to find the token whose inner product with that token is smallest. In nonnegative kernel attention, as opposed to softmax attention, one forms kernel embeddings ϕQ,ϕK\phi_Q, \phi_K for query and for key for each token into an rr-dimensional feature space, with the extra constraint that the kernel operator is entrywise nonnegative (i.e. ⟨ϕQ(x),ϕK(y)⟩≥0\langle\phi_Q(x), \phi_K(y)\rangle \ge 0 for all possible tokens x,yx,y. The pairwise overlaps given by this kernel are then normalized, yielding convex combination vectors in analogy with standard softmax attention, and the output of the mechanism on token ii is given by passing the corresponding convex combination of the tokens through a linear decoder which depends only on that token.

The main finding of the paper is that for sequences of length ≥3\ge 3, the minimum inner product problem requires exponential in token dimension mm (in contrast, softmax attention has no such representational issues). The author(s) also show that this issue does not go away with multi-head attention. If the decoder is allowed to be a degree-DD polynomial, then the exponential lower bound kicks in at sequence length D+2D + 2. On the other hand, if the decoder is arbitrary, then one can cheat by using infinite precision, but with finite precision they show a lower bound on the number of bits that tokens must communicate. The work also includes some synthetic experiments to validate these findings.

Critical strengths
  • The message is clear: there is a relatively simple and natural retrieval task that linear attention is provably ill-suited for, and it kicks in even at tiny sequence lengths.
  • Beyond the basic mechanism, the paper also gives several extensions.
Critical weaknesses
  • As the paper itself observes, the phenomenon is a little artificial if one parametrizes the decoder solely by degree. If you have a ReLU decoder, then the lower bound goes away. This weakens the motivation for considering the particular theoretical setting studied in this paper.
  • At this point there have been many separations between linear attention and transformers, as well as empirical findings that the former are not good at certain retrieval tasks (e.g., Jelassi et al.), which limits the conceptual novelty of the findings.
Questions for authors
  • Are there harder problems than Min-IP for which even allowing ReLU in the decoder requires exponentially large feature dimension?
1 comment

Thank you for your comments, which helped us strengthen the paper. Our general comment provides an overview of the changes made.

Weaknesses: Motivation with ReLU readouts

We agree that unrestricted ReLU readouts change the picture, so we have added a normalized-sensitivity tradeoff for general nonlinear readouts (Theorem 2).

Weaknesses: Distinction from prior work

Copying and recall impossibility results such as those of Jelassi et al. (2024) and Arora et al. (2024) are concerned with information storage (how much information can be stored in a fixed-size state?). Our affine impossibility result concerns information use (how can information be aggregated and decoded through a shared summary?), giving us some intuition about the attention mechanism itself.

For Min-IP over three tokens, deterministic one-way communication complexity is Θ(m)\Theta(m), while one head with a nonnegative kernel and an affine readout requires 2Θ(m)2^{\Theta(m)} features, even with exact arithmetic and value vectors of arbitrary finite dimension. The two types of bounds address different resources, so our result complements the information-storage viewpoint.

Question: Can harder tasks require exponential feature rank with ReLU readouts?

Choosing a harder task alone does not prevent the escape when positional values of arbitrary finite width are allowed. At a fixed sequence length, the construction in Section 5 stores the entire input in a uniform rank-one head, so an unrestricted ReLU decoder can compute any function on our finite input domain. For this reason, we need an additional restriction, and the construction motivated us to study normalized sensitivity. This cannot be reduced by rescaling the values and lets us compare with dense softmax at K=mK=m. Other tasks may call for different decoder budgets.

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

This paper studies how many kernel features normalized nonnegative linear attention needs to compute Min-IP, the minimum overlap between a query token and every token in the sequence. It shows a sharp threshold: one feature suffices for two tokens, but three tokens already require exponential feature rank for one head with an affine readout, while dense softmax solves the same task easily. The authors extend this to multiple heads and polynomial readouts, add a communication lower bound for multi-layer models with finite precision, and include small synthetic experiments illustrating the proof mechanism.

Critical strengths
  1. The paper's idea is elegant and I like the transition from two tokens to three tokens. it is very sharp.

  2. To the best of my knowledge, the proofs and mathematical arguments are sound.

  3. The paper is clearly written and easy to follow.

Critical weaknesses
  1. I am concerned with the scope of the setting. The bound requires one layer, an affine readout, and a nonnegative normalized kernel, and Appendix C.2 shows that a single ReLU readout with positional values already solves the three-token task at rank one. Modern linear-attention variants such as DeltaNet or Mamba-2 are also not covered, so the practical relevance is limited.

  2. The relationship to prior work could be developed further. The trace and Frobenius rank estimate should also be situated relative to classical results on perturbed identity matrices, such as Alon (2009). Sanford, Hsu, and Telgarsky (2023) provides relevant context on pair and triple detection and communication complexity, although its task and resource bounds differ from those studied here.

  3. The multi-head bound is only meaningful at very large m. The required overlap gap grows quickly (172 for two heads, 5,468 for three), so the exponent is roughly m/1376 for H = 2 and becomes vacuous at realistic widths.

  4. The experiments add little to the theory. Section 6.1 runs at m = 24, where the theorem only certifies r<9r<9, and training fails even where a solution exists.

I would be open to increasing my score if the authors clarify the scope of the contribution, how it differs from prior work, how the experiments support the theoretical results, and what practical implications follow from the findings.

Questions for authors

Please see Weaknesses section.

3 comments

Thank you for your comments, which helped us strengthen the paper. We address your points below. Our general comment summarizes the changes in the revised version.

Weaknesses: Scope and practical relevance

Theorem 2 now covers general nonlinear readouts (including ReLU networks) for one layer with H≥2H\ge2 heads and position-independent nonnegative kernels. Values may depend on position, and the readout has a budget on normalized sensitivity. Matching dense softmax's sensitivity requires total feature rank 2Ω(m/H)2^{\Omega(m/H)} on sufficiently long sequences. The rank-one escape also has a cost: its readout must become more sensitive as the sequence grows (Theorem 4).

Section 8 discusses ELU+1, normalized FAVOR+ with fixed positive features, and Hedgehog layers within this one-layer setting. Signed kernels, multiple attention layers, and the state updates of DeltaNet and Mamba-2 remain outside the rank bounds, and extending our analysis to these settings is an interesting direction for future work. Only Theorem 11 addresses multiple layers, through finite-alphabet communication, an approach also used in prior work.

Weaknesses: Relation to prior work

Thank you for pointing out these works, we now cite Alon (2009) for rank bounds on perturbed identity matrices. Our contribution is (i) showing that Min-IP correctness on every input forces uniform kernel preferences and (ii) amplifying these preferences into a matrix to which the classical rank estimate applies. Sanford, Hsu and Telgarsky (2023) also consider detecting triples of tokens, but use finite-precision communication and obtain bounds that scale with sequence length. Our three-token affine result fixes sequence length and bounds kernel factorization rank as token dimension grows, allowing exact arithmetic and arbitrary finite value width. These communication bounds concern how much information must be transmitted, while our result concerns how the attention mechanism can aggregate and decode that information (which studies the mechanism itself). Table 3 compares the resources bounded by related work.

Weaknesses: Finite multihead bounds

The original multihead bound applies to very short sequences (n=H+2n=H+2), but its constants are large. Allowing longer sequences gives a more useful finite guarantee: for example, with two heads and m=256m=256, the original explicit estimate gives no nontrivial finite bound at n=4n=4, while at n=12n=12 we obtain R≥46,401R\ge46{,}401 (Theorem 9). Both cases assume affine readouts and position-independent kernels and values, with no sensitivity budget.

Weaknesses: Experiments

You are right that training failure does not imply lack of expressivity. Our explicit rank-15 solution makes this distinction concrete: the model can represent a solution even when our training procedure does not find it. The experiments serve as small-scale illustrations of the proof mechanism, with Figure 1c comparing the amplification ratios of successfully trained models against the theoretical requirement. We have clarified this interpretation in Section 6.

Reviewer_g12fOpenReview ↗

Reply to Authors Rebuttal

I thank the authors for the detailed response and the substantial revisions.

However, my main concern about scope remains. The new result for nonlinear readouts (Theorem 2) relies on a normalized-sensitivity budget that appears to have been introduced specifically to exclude the rank-one ReLU construction, and its justification as a natural resource beyond that purpose is limited. Moreover, the rank-one escape requires sensitivity of only Θ(mn)\Theta(mn), so avoiding exponential feature rank costs sensitivity that grows linearly in sequence length. This is a comparatively mild cost and weakens the claim that comparison is “never free.” The exponential separation therefore still depends substantially on restricting the readout. Practical relevance also remains limited, since DeltaNet, Mamba-2, signed kernels and multi-layer models fall outside the rank bounds, and the multi-head three-token bound remains vacuous at realistic widths.

I also note that the experiments are now framed as illustrations of the proof mechanism, which is appropriate, but they do not provide additional support for the theoretical claims. For these reasons, I maintain my score.

Thank you for the follow-up. We find these points reasonable and will consider them for future work.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of revisions

First of all, we thank the reviewers for their time and valuable comments.

We revised the manuscript in response to the reviewers' comments. The main changes are listed below, and we will give detailed responses to each reviewer separately.

  • Nonlinear readouts (all): All reviewers commented on nonlinear readouts. We added Theorem 2, which provides guarantees for a single layer with position-independent nonnegative kernels and general (possibly nonlinear) readouts with normalized sensitivity KK. As a consequence of Theorem 2 and Corollary 3, we show that when K=mK=m, H≥2H\geq 2 heads require a total of 2Ω(m/H)2^{\Omega(m/H)} features for sufficiently long sequences. On the other hand, for a fixed number of heads HH, polynomially many features require K=Ω(mn/log⁡m)K=\Omega(mn/\log m). We also show that the “escape” using rank-one attention with a ReLU readout has sensitivity Θ(mn)\Theta(mn). Note that without restricting the readout, even rank-one attention can solve arbitrary tasks using positional values (see Section 5).

  • Finite guarantees (g12f): We added Theorem 9, which provides guarantees for longer sequences with affine readouts. This result does not impose a budget on the readout's sensitivity. In Table 2, we provide examples of feature rank lower bounds for different sequence lengths at dense softmax's sensitivity.

  • Motivation (9nqg, wPzj): We added a discussion in the introduction explaining (i) why we study attention mechanisms with nonnegative kernels, as used in many practical designs, (ii) why we study Min-IP to isolate the cost of factoring the kernel matrix, and (iii) how our results differ from separations based on information capacity.

  • Scope and practical implications (g12f): We added a paragraph in Section 8 clarifying that models such as DeltaNet and Mamba-2 are outside the scope of our rank bounds. We also briefly discuss implications for linear attention with positive features.

  • Related work (g12f, wPzj): We added a discussion of Alon (2009), Sanford et al. (2023), Jelassi et al. (2024), and Hahn (2020) to the related work section.

  • Abstract (9nqg, wPzj): We revised the abstract for clarity.

  • Clarity (9nqg, wPzj): In Section 3.1, we introduce constant-weight codes and their distance. We also state and explain the trace–Frobenius inequality before using it.

  • Results summary (9nqg, wPzj): We added a table (Table 1) summarizing our main results along with their corresponding theorem numbers.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.