# Three Tokens Force Exponential Feature Rank in Nonnegative Kernel Attention

arXiv: https://arxiv.org/abs/2608.11427 · HTML: https://mlsanity.com/paper/2608.11427/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 21 references that are in the map.
- First posted on arXiv 11 Aug 2026.

## Builds on (most cited first, 19 of 19)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Simple linear attention language models balance the recall-throughput tradeoff](https://mlsanity.com/paper/2402.18668/) (2024)
- [On the Theoretical Limitations of Embedding-Based Retrieval](https://mlsanity.com/paper/2508.21038/) (2025)
- [Low-Rank Bottleneck in Multi-head Attention Models](https://mlsanity.com/paper/2002.07028/) (2020)
- [Transformers, parallel computation, and logarithmic depth](https://mlsanity.com/paper/2402.09268/) (2024)
- [Separations in the Representational Capabilities of Transformers and Recurrent Architectures](https://mlsanity.com/paper/2406.09347/) (2024)
- [Fundamental Limitations on Subquadratic Alternatives to Transformers](https://mlsanity.com/paper/2410.04271/) (2024)
- [ZeroS: Zero-Sum Linear Attention for Efficient Transformers](https://mlsanity.com/paper/2602.05230/) (2026)
- [Multi-Vector Embeddings are Provably More Expressive than Single Vector Embeddings](https://mlsanity.com/paper/2606.23475/) (2026)
- [Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity](https://mlsanity.com/paper/2607.20393/) (2026)
- [The Effect of Attention Head Count on Transformer Approximation](https://mlsanity.com/paper/2510.06662/) (2025)
- [Kernelized Linear Attention: Breaking the Capacity Wall with Symmetric Cones](https://mlsanity.com/paper/2607.17419/) (2026)
- [Provably Learning Multi-Head Attention with Queries](https://mlsanity.com/paper/2608.03294/) (2026)
- [A Provable Expressiveness Hierarchy in Hybrid Linear-Full Attention](https://mlsanity.com/paper/2602.01763/) (2026)
- [The Impossibility Triangle of Long-Context Modeling](https://mlsanity.com/paper/2605.05066/) (2026)
- [Attention-based representations for multi-task computation](https://mlsanity.com/paper/2608.04243/) (2026)

## Abstract (arXiv)

How much feature rank does comparison require in kernel attention? On Min-IP over m-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 2Theta(m) for error strictly below 1/2 on every input, even with arbitrary finite-dimensional tokenwise values and query-dependent affine readouts. Dense softmax solves this three-token task with m-dimensional scores and temperature constant in m. For every fixed number of heads H, the minimum total feature rank is 2ThetaH(m) for the same error guarantee at exact length H+2 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 D, rank one suffices at exact length D+1, while exact length D+2 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 n requires Omega(nlog m) bits over a range of lengths that grows exponentially with m.