Minimax Sample Complexity of Full and Low-Rank Bilinear Attention Score Estimation

In attention models, the projection dimensions of queries and keys bound the rank of pre-softmax score matrices, yet the statistical benefit of this low-rank structure for attention score estimation remains insufficiently characterized. To this end, we show that exploiting low-rank structure reduces the sample complexity of score estimation from limited token-pair data, and quantify the gap between the full-matrix and rank-$r$ classes in a noisy rank-1 observation model. For $d$-dimensional representations, we prove minimax lower bounds for squared Frobenius error with dimension factors $d^2$ and $2dr-r^2$ for the full-matrix and rank-$r$ classes, respectively, under independent isotropic sub-Gaussian inputs and Gaussian noise. Correspondingly, global least-squares solutions satisfy matching-order high-probability upper bounds, with dimension factors $d^2$ and $rd$. As a convex alternative to rank-constrained estimation, nuclear norm penalized least squares attains the same $rd$ dependence under independent sub-Gaussian noise. Together, the lower and upper bounds establish an order-$d/r$ sample-complexity advantage for rank-$r$ estimation at matched accuracy and confidence under Gaussian noise.