Three Tokens Force Exponential Feature Rank in Nonnegative Kernel Attention

Excerpt

arXiv:2608.11427v2 Announce Type: replace Abstract: 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 $2^{\Theta(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-tok