My main concerns regard the positioning of the contribution relative to previous work and the interpretation of the attention experiments. I find the finite sample guarantees useful, but I think the manuscript should distinguish more clearly what is established in this paper from the existing understanding of low-rank learning.
First, I noticed that the related work discussion misses several analyses of attention, quadratic networks, and overparameterized matrix estimation that I believe are closely connected to this work. In the abstract, the authors state that the statistical benefit of low-rank structure for attention score estimation "remains insufficiently characterized." I think the question of what is missing should be formulated more precisely. Previous works already study recovery of low-rank matrices through overparameterized factorizations [1], the effects of target and architectures widths on recovery and generalization in quadratic networks [2], and Bayesian [3] and empirical risk minimization [4] analyses of attention when varying the key/query ranks. In particular, [4] compares factorized and nonfactorized attention estimation, while [5] connects weight regularization in quadratic networks to matrix estimation with a nuclear norm penalty. These are, in my opinion, substantial connections to the motivation of the present paper. Some of these works provide sharp high-dimensional predictions, whereas the present results give finite dimensional minimax results; others study related recovery problems under different measurement and optimization assumptions. I think the authors should discuss the connections of their work with these lines of related works and explain their relationships and differences.
There is also a close relationship to the classical matrix estimation results already cited by the authors. [6] obtain low-rank recovery rates under noisy rank-one measurements, while [7] provide a curvature result applicable to the present input assumptions. The authors acknowledge these two works and they explain further differences in the least squares objectives, input coordinates, and probability bounds. However I would appreciate a clearer explanation of which part of the final guarantee goes beyond [6] and [7], and what additional argument is needed to establish it. This would make the authors' contribution easier to assess rather than emphasizing mainly the d2/n versus rd/n scaling, which is already familiar from low-rank estimation.
Second, I think the message about attention width needs some qualification. In theorem 5 the authors compare estimating an arbitrary matrix with bounded Frobenius norm against estimating a target assumed to have rank at most r. The first problem must also handle high-rank targets, so to me this is not a direct comparison of two architectures learning the same low-rank target. In fact, in theorem 4 the authors show that one can fit an unrestricted matrix and still obtain an error bound of order σ2rd/n through nuclear norm regularization (fixed confidence and under the sample size conditions they state). This is interesting but it also means that reducing the fitted width is not necessary to obtain the low-rank statistical benefit. I would make this distinction explicit in the motivation for narrower query and key projections.
Regarding the experiments, I find section 6.3 useful as a qualitative case study, but its conclusions depend on the estimator comparison. If I understood correctly the authors fit bilinear predictors to scores from two heads of a frozen BERT model. In figure 3 the low-rank estimator has both a rank constraint and a Frobenius norm bound, whereas ordinary least squares has neither. The improvement can therefore reflect both restrictions, rather than the rank constraint alone. The authors also compare estimators with the same norm bound, and these comparisons favor low-rank fitting in one head and full-matrix fitting in the other. I appreciate that this is reported, but I think it should be more central to the interpretation of Figure 3. Comparisons against ridge (tuned over the regularization) and least squares with nuclear norm penalty on the same task would also help clarify if small rank offers an advantage over regularizing a full matrix.
In the end, despite the weaknesses stated above, I personally lean towards weak acceptance. My positive assessment is based mainly on the theoretical guarantees presented by the authors, and I would appreciate the authors' response to the related work and empirical concerns above. I am happy to maintain or raise the score in case my concerns are addressed.
[1] Li, Y., Ma, T., and Zhang, H. Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations. COLT, 2018.
[2] Martin, S., Biroli, G., and Bach, F. High-Dimensional Analysis of Gradient Flow for Extensive-Width Quadratic Neural Networks. JMLR, 2026.
[3] Boncoraglio, F., Troiani, E., Erba, V., and Zdeborová, L. Bayes optimal learning of attention-indexed models. NeurIPS, 2025.
[4] Boncoraglio, F., Erba, V., Troiani, E., Xu, Y., Krzakala, F., and Zdeborová, L. Single-Head Attention in High Dimensions: A Theory of Generalization, Weights Spectra, and Scaling Laws. ICML, 2026.
[5] Erba, V., Troiani, E., Zdeborová, L., and Krzakala, F. The Nuclear Route: Sharp Asymptotics of ERM in Overparameterized Quadratic Networks. NeurIPS, 2025.
[6] T. T. Cai and A. Zhang. ROP: Matrix recovery via rank-one projections. The Annals of Statistics, 2015.
[7] N. Hamidi and M. Bayati. On low-rank trace regression under general sampling distribution. JMLR, 2022.
We thank you for the careful reading and for the direct questions on novelty and model scope.
[W1] What is novel. We agree that Eq. (1) is the classical trace-regression / matrix-sensing model with rank-1 measurements. Appendix D makes this connection explicit and quantitative. The two-term dimension scaling matches Cai & Zhang (2015), and we verify that our inputs satisfy Hamidi & Bayati (2022) Thm. 3.2 by checking their Assumption 3.3 and the required operator-norm bound. We will restate the contribution as a specific finite-sample comparison in the revised paper and made the division of labor explicit in two parts.
[W2] Scope of the attention model. We accept that our model is a simplification. The estimand is the pre-softmax query–key interaction matrix. Sec. 2 states that the fixed attention scaling is absorbed into M∗, Sec. 2.2 identifies A=WQ⊤WK (equivalently WqWk⊤/dh under the row-vector convention), and Appendix "Prediction of pretrained BERT attention scores" verifies the label implementation against the model's query and key linear layers on sampled token pairs. Softmax normalization, value aggregation and interactions among heads are not covered and are listed as future work in the Conclusion. To make the model scope explicit, we will add a scope paragraph stating that the bilinear reduction is exact when queries and keys are linear in the inputs and that it does not model the softmax or value path. The statistical bounds also assume isotropic, independent inputs, which is a separate assumption from the bilinear form itself. This keeps the distance from Softmax(QK⊤/d)V explicit. We will also relate this target to linear-attention formulations (Katharopoulos, 2020), which use a different kernelized attention computation, whereas we study the original pre-softmax QK⊤/dh interaction matrix.