acceptodds
Under review as a conference paper at ICLR 2027

An Infinite Information Exponent that Gradient Descent Still Learns at the Optimal Rate: The Value Catalyst in Softmax Attention

Abstract

The information exponent of a single-index target describes how gradient descent learns it: an exponent- target can trap online SGD for samples, while an infinite exponent ordinarily indicates a direction that gradient descent cannot recover. We show that this interpretation fails for a coupled attention model. Consider a softmax head that selects a token through a key direction and reads a scalar through an orthogonal value direction , The selection direction has infinite information exponent: the label is mean-zero conditional on the key scores, so every key-only correlational query and every single-index surrogate gradient vanishes. Nevertheless, projected gradient descent on the invariant slice of the coupled key-value loss learns with samples per step; unrestricted random initializations exhibit the same cascade numerically. The value direction has information exponent one; once it is partially learned, the key gradient gains the explicit component where and is the mean softmax collision probability. This value catalyst produces a value-to-selection cascade with dimension-free population convergence. Squaring the label exposes the same selection direction at generative exponent two and yields a one-step spectral estimator with a linear dimensional exponent up to logarithmic factors. For every noise level, an oracle lower bound that reveals all exact key scores still requires samples for constant projective accuracy; at fixed positive noise, a Fano bound additionally gives explicit parameter dependence. The phenomenon extends to additive and multiplicative combinations of orthogonal-subspace heads, and CPU experiments check the predicted gradients, spectra, and scaling laws.

Primary area:
learning theory
Keywords:
attention, gradient descent, information exponent, generative exponent, sample complexity, learning theory, spectral methods, statistical query lower bounds

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.25 over 4 reviews, above 2% of the others.
Reviewer_wLeiOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies gradient descent learning of the key and value component in a simple softmax attention unit. One of the main observations is that selection direction cannot be learned through correlation of only the labels and key scores. However, by introducing also learnable value scores, learning the selection direction becomes subsequently tractable. Thus, the main contribution of the paper is to characterize a mechanism by which learning first a value direction helps with learning of the selection direction. The authors do this analysis in the context of the sample complexity for the projected gradient descent under certain technical assumptions on the model and initialization and a spectral method using the squared labels. The authors support the derived theory results with numerical experiments.

Critical strengths

I see the following as strengths of this paper.

  1. The topic of joint learning seems quite interesting and specifically how you can clearly see numerically that the value direction is learned first and subsequently followed by the learning of the selection direction. What is also nice is that this phenomenon is already exhibited in a quite simple model, which gives clean setting for theoretical analysis.

  2. The paper has an interesting theoretical results that are a good step towards understanding the joint learning dynamics of the attention model. In particular I find that Theorem 1 gives a useful insight into where this "value catalyst" phenomenon comes from.

Critical weaknesses

I have found two main weakness points.

  1. The main weakness is regarding the proof and implications of the theory contribution of the paper. One of the main results, the optimal O(d)O(d) sample complexity bound coming from Theorem 6 in appendix, crucially relies on the invariant subspace introduced in Lemma 11 through Theorem 5. Even though this subspace is indeed invariant under population gradient updates, and sample gradients concentrate, the subspace is not necessarily invariant under finite sample updates considered in Theorem 6. Thus, as it currently stands, it is unclear whether the current main convergence result holds. Next, the learnability gap coming from Corollary 1 and Theorem 2, seems a bit misleading. Namely, the gap exists because of the restriction imposed on looking at this as a single-index model by only using key scores correlation, even though it is multi-index and value scores are available. There is also the orthogonality assumption between the selection and value vector. As commented in Remark 1 of the paper, the gap disappears once there is correlation between the vectors value and key vectors. I believe it can be argued that this is not necessarily a generic situation, as even if they would be independently sampled random variables, their overlap would be non-zero. It would be nice to see stronger justification of these assumptions and/or a mechanism explaining hardness of learnability of selection direction. Overall, this weakness raises soundness and informativeness concerns for me.

  2. Presentation of the paper, even though understandable, requires quite a bit of effort to follow. Namely, exposition is very dense, important results and assumptions are scattered across the main body and appendix (e.g. Theorem 6, one of the main results of the paper even motivating the title, is located in the appendix and only abruptly referenced in the main body; for the definition of invariant space, crucial for the results in the main body, one needs to look up Lemma 11 in the appendix) and what is more, most of the important quantities used in the introduction are only introduced in subsequent section and understandable after reading that sections first. This makes following arguments and main results more challenging.

Questions for authors
  1. Can you please justify the finite sample analysis of Theorem 6, since finite sample updates do not necessarily land in the invariant subspace of Lemma 11 and Theorem 5?

  2. Can you please explain how is the gap from Corollary 1 and Theorem 2 related to the hardness of learning the selection direction for the general multi-index setting considered, instead of being an artifact of restricting the analysis to the single-index setting?

  3. Can you please justify the orthogonality assumption in more detail? Also, could you expand on the brief discussion from Remark 1 on how the theoretical analysis and possible conclusions would change if instead there was a (small) overlap between the selection and value vectors?

Reviewer_rz7fOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper studies one softmax attention head with LL Gaussian tokens. The label is a softmax average of value scores ⟨u⋆,xi⟩\langle u^\star,x_i\rangle, with weights set by key scores ⟨w⋆,xi⟩\langle w^\star,x_i\rangle and w⋆⊥u⋆w^\star\perp u^\star. Because the values have mean zero and are independent of the keys, the label is uncorrelated with every function of the key scores. The paper calls this an infinite information exponent for w⋆w^\star. Squaring the label exposes a degree-two signal, which gives a generative exponent of two.

The main result is that projected gradient descent on a key–value student still learns w⋆w^\star. On an invariant slice, the loss is exactly Pˉ−μC(m)\bar P-\mu C(m). Here mm and μ\mu are the key and value overlaps, and CC has nonnegative Mehler coefficients. So a positive value overlap drives the key overlap toward one. Theorem 5 gives O(log⁡(1/ϵ))O(\log(1/\epsilon)) dimension-free population steps, and Theorem 6 claims O(dϵ−2)O(d\epsilon^{-2}) fresh samples per step. The paper also gives a spectral estimator and two lower bounds.

Critical strengths

The model is clean, and introduction lays out the setup in an intriguing way. The paper is also candid about its scope: Remark 3 states that convergence is only proved on the slice, Remark 5 lists the gaps in the constants, and Remark 6 separates the parts that depend on Gaussianity.

Critical weaknesses

This paper feels half-finished. There are very striking issues with the presentation and formatting. Figure 1's caption says the single-index SGD comparison "is not plotted here", while Section 7 says Figure 1 shows it stalling. Also, in many places including caption of Figure 1, there are dangling references to local files such as python scripts. The blocks of text for the various statements and corollaries are dense and hard to read; the statement of remark 6, for instance, is honestly some of the longest italicized text blocks I have seen. This problem gets much worse in the appendix, e.g., Appendix F looks like a dump of information without basic filtering or formatting.

The headline framing is not adequately justified. IE and GE have their familiar complexity interpretations in single-index models, whereas this attention head is explicitly multi-index, depending jointly on key and value scores. Its infinite IE only concerns functions of the teacher's key scores, ignoring the value and mixed key-value signals available to joint training. The leap/staircase framework of Abbe et al. (2023) already describes how learning some directions exposes others. The paper cites this work but does not discuss the leap complexity of the current problem, how shared parameters across tokens affect the comparison, or why efficient joint GD despite this marginal infinite IE should be surprising. Without such a comparison, the emphasis on IE/GE does not establish what is new beyond a familiar multi-index learning hierarchy.

The comparison with prior attention dynamics is also incomplete. Marion et al. (ICLR 2025), not cited here, already analyze projected GD for orthogonal key/value vectors on the same invariant slice. Their activation and data model differ, but the paper should explain what new technical obstacle its softmax analysis resolves.

The broad claims about "every correlational query" and "any single-index surrogate" are also false as written. Applying the Lemma 8 argument to the raw label gives ∑iE[y(xixi⊤−I)]=β(1−Pˉ)(w⋆u⋆⊤+u⋆w⋆⊤)\sum_i\mathbb{E}[y(x_ix_i^\top-I)]=\beta(1-\bar P)(w^\star u^{\star\top}+u^\star w^{\star\top}), exposing span{w⋆,u⋆}\mathrm{span}\{w^\star,u^\star\} without squaring the label. For square loss with student y^θ=12∑i(θ⊤xi)2\widehat y_\theta=\frac12\sum_i(\theta^\top x_i)^2, this yields ⟨∇θL,w⋆⟩=−β(1−Pˉ)≠0\langle\nabla_\theta\mathcal L,w^\star\rangle=-\beta(1-\bar P)\neq0 at θ=u⋆\theta=u^\star. The teacher-key conditional-mean identity does not imply either blanket claim.

There are also specific proof issues:

  • Theorem 6 lacks off-slice control. Fresh-batch noise breaks the population invariant conditions q=⟨w,u⟩=r=⟨w,u⋆⟩=p=⟨w⋆,u⟩=0q=\langle w,u\rangle=r=\langle w,u^\star\rangle=p=\langle w^\star,u\rangle=0, even after sphere projection. Gradient concentration alone does not control the subsequent drift or establish the claimed O(dϵ−2)O(d\epsilon^{-2}) samples per step. An off-slice stability estimate is missing; this is a proof gap, not a counterexample to convergence.
  • Theorem 5 has a repairable rate error. At m=μ=0m=\mu=0, the normalized value update gives μ+=(η/L)/1+(η/L)2<η/L\mu^+=(\eta/L)/\sqrt{1+(\eta/L)^2}<\eta/L. By continuity, the claimed contraction 1−μt+1≤(1−η/L)(1−μt)1-\mu_{t+1}\le(1-\eta/L)(1-\mu_t) fails for sufficiently small permitted positive overlaps. The selection bound has the same normalization issue. Constant-factor rate corrections and a suitable step size should preserve geometric convergence, but the displayed rates and TpopT_{\mathrm{pop}} need revision.
  • Lemma 15 is false as stated. The nonconstant, radially nondecreasing function F(z)=1{z1>0}F(z)=\mathbf 1\{z_1>0\} has Cov(F(Z),∥Z∥2)=0\mathrm{Cov}(F(Z),\|Z\|^2)=0, since Gaussian radius and direction are independent. Strict positivity requires strict radial increase on a positive-measure set of directions. Lemma 5 supplies this for the collision probability, so the GE=2\mathrm{GE}=2 conclusion survives.
  • Corollary 3 calls the ordering "forced", but gives a random-walk heuristic without a precise time window or high-probability argument controlling off-slice motion.
Questions for authors

How does this head relate to existing leap/staircase analyses, including its low-degree mixed key-value signals and shared parameters across tokens? What does the marginal IEw⋆=∞\mathrm{IE}_{w^\star}=\infty explain about joint GD that this multi-index perspective does not?

Reviewer_fSbZOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The submission provides an example of high dimensional inference model close to single/multi index line of works. The novelty of the model is that even though it has a "selection direction" with infinite information exponent, it can still be learned by a simple attention network that leverages gradient signal coming from a learnable value direction.

Critical strengths

The proposed principle is interesting and the connection to attention networks is promising.

Critical weaknesses
  • The comparison to single index models and information and generative exponents is misleading. More precisely, the predictions on sample complexity and relations to CSQ/ SQ frameworks depend on properties of the loss function on which gradient based algorithms are applied. The loss function optimized in this work depends on two directions (selection and value), hence the correct comparison should be with multi-index models. So singling out the information exponent only of the "selection" direction is misleading since it is not the single relevant quantity to establish the behavior of gradient descent on this model, even by standard single/multi index analysis.
  • in multi-index literature there are works that already show the so called "staircase behavior" and in [1] the following example appears: y=z1+z1z2y=z_1+ z_1z_2, where z1z_1 and z2z_2 are projections with respect to orthogonal directions. This seems to present same core property as the model proposed in the submission : E[y∣z2]=0\mathbb E[y|z_2]=0 even though networks can learn both direction at linear sample complexity. Hence the main mechanism shown in the submission has really close antecedents that were not discussed. It is especially relevant since this was presented as one of the core contributions.
  • The connection to attention networks is not explored enough to make it a stand alone contribution. It is not clear whether the mechanism identified in the submission is purely a theoretical proof of concept or can be relevant for the practical performance of transformers.

References: [1] Luca Arnaboldi, Yatin Dandi, Florent Krzakala, Luca Pesce, and Ludovic Stephan. Repetita iuvant: Data repetition allows sgd to learn high-dimensional multi-index functions. arXiv preprint arXiv:2405.15459, 2024.

Questions for authors

Can other architectures learn the structure or is it specific to attention?

Reviewer_WSz4OpenReview ↗
Rating
2
Confidence
4
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper analyzes the information/generative exponent of a single layer attention network. It is shown that the selection direction has IE=∞\mathrm{IE}=\infty under an orthogonality condition, but its population gradient has a correlation linear to the value direction alignment. This is quite different from the usual single index model analysis. Moreover, the information exponent with respect to the value direction is 1 and thus the GD can easily recovers the value direction, which eventually make it possible to identify the selection direction with optimal rate even though IE=∞\mathrm{IE}=\infty. In other words, recovery of the value direction helps to find the selection direction like catalyst. This observation matches the fact of GE=2\mathrm{GE}=2.

Critical strengths
  • I think the finding of difference from the single index analysis is interesting. In the attention setting, the small alignment of the value direction easily breaks the orthogonality of the population gradient leading to optimal near optimal sample complexity to recover the selection direction, which is interesting.
  • The synthetic numerical experiments matches the theoretical finding, that is, first the value direction is recovered and second the selection direction is recovered. The theoretical analysis gives some insight into the practical behavior of transformers, rather than pure mathematical interest.
Critical weaknesses
  • On the other hand, it is quite natural to get IE=1 when μ≠0\mu \neq 0 because exp⁡(⟨w,x⟩)\exp(\langle w,x \rangle) has IE=1 and this information of w⋆w^\star can be retrieved when there is a correlation between ⟨u,x⟩\langle u,x \rangle and ⟨u⋆,x⟩\langle u^{\star},x\rangle. Therefore, I did not feel there is a deep mathematical insight behind the analysis.
  • The orthogonality between u⋆u^{\star} and w⋆w^{\star} is a bit strong assumption. It is more natural to consider that there is a small correlation (at least 1/d1/\sqrt{d}) in practice. In that sense, the applicability of the theoretical setting is limited.
  • The writing can be improved a little bit more. Actually, some lemmas that appear later are referred in remarks, which forces me to read the paper back and forth. Even lemmas in appendix are referred in the main text. The writing of the main text can be more organized so that we can read the paper in a straight way.
Questions for authors
  • As for my general concerns, please see the "weakness".
  • Is it observed in practical transformers that the value directions are aligned first before the selection direction is obtained?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.