Three Tokens Force Exponential Feature Rank in Nonnegative Kernel Attention
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,...