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