acceptodds
Under review as a conference paper at ICLR 2027

Training Dynamics of Large State-Transition Models

Abstract

Jointly learning input and output embeddings is common practice in modern neural sequence models, yet it remains unclear when gradient-based training can successfully optimize these coupled components to achieve accurate predictions. We study this question in a softmax state-transition model with a learned state embedding and prediction head, trained from Gaussian initialization using exact population gradients. We consider a model with states and embedding dimension , where the ground-truth transition law’s row-centered log-probability table has low rank and bounded entries. We measure prediction quality by relative prediction gain (RPG), normalized so that uniform prediction has gain zero and optimal prediction has gain one. We provide analysis for both untied and tied models. With an untied model and weight decay of order , we show that perturbed gradient descent achieves RPG above in polynomial time when . With probability at least where , this holds at every iterate in the final fraction of the run while perturbations remain at a fixed scale. For tied embeddings, we provetraining guarantees on the observed current states, and under the assumption of ground-truth feature coverage and bounded learned rows, we prove prediction guarantees on unseen current states. We present numerical experiments with practical parameter choices that qualitatively illustrate persistent training gain and tied-model transfer.

Primary area:
learning theory
Keywords:
Training dynamics, state-transition model, Non-convex optimization, Gradient-descent

Reviews

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

This paper studies when joint training of low-dimensional input/output embeddings can learn a large softmax state-transition model. The main result shows constant prediction gain for perturbed gradient descent at width d=Ω(V)d=\Omega(\sqrt V), with additional results for tied embeddings and transfer to unseen input states. I think there is real technical novelty here: the trace-based curvature argument improves the direct generic comparison from O(V/d)O(V/d) to O(V/d2+1/d)O(V/d^2+1/d). I did not find a clear correctness issue in the main results. My main concern is significance. The topic is relevant to ICLR, but I am not yet convinced that the current theorems tell us something important enough about actual training dynamics. I am therefore leaning weak reject.

Critical strengths
  • There is a concrete new technical idea. The trace-packing argument in Appendix B.4 uses the total categorical curvature budget and obtains O(V/d2+1/d)O(V/d^2+1/d), while the direct generic factorized bound gives only O(V/d)O(V/d). This is what makes the d=Ω(V)d=\Omega(\sqrt V) guarantee possible.

  • The main theorem is stronger than a stationary-point result. Thm 4.1 controls every iterate in the final 1−1/d1-1/d fraction of the run. The repeated-SOSP-visit plus objective-refresh argument is nontrivial and directly addresses the training trajectory.

Critical weaknesses
  • Significance: the novelty is real, but I am not convinced what the V\sqrt V guarantee tells us about learning. The target is already representable when d≥rd\ge r, while thn 4.1 needs d=Ω(V)d=\Omega(\sqrt V). The paper does not show that this gap is necessary, close to necessary, or associated with an actual optimization barrier. At the moment, this looks more like a technically interesting sufficient condition than a strong explanation of training dynamics.

  • Scope: the strongest transfer result remains conditional on an important property that training itself does not establish. Thm 5.4 requires centered coverage and uniformly bounded learned rows, and the paper explicitly states that the optimization analysis does not prove the learned-row condition. This makes the transfer result less satisfying as a statement about what the proposed training algorithm actually learns.

Questions for authors
  1. Is there any evidence that the d=Ω(V)d=\Omega(\sqrt V) scale is intrinsic? For example, can the authors give a lower bound, hard instance, or failure mode below this scale?

  2. Can the bounded learned-row assumption in Thm 5.4 be proved from the training dynamics, or substantially weakened?

  3. Beyond improving the sufficient width bound, is there a stronger consequence of the trace-based argument that would distinguish a genuine learning phenomenon from proof slack?

3 comments
AuthorsOpenReview ↗

Responses to Weaknesses

We thank the reviewer for careful reading and thoughtful comments. We provide detailed responses below.

W1: Significance: the novelty is real, but I am not convinced what the V\sqrt{V} guarantee tells us about learning. The target is already representable when d≥rd\geq r, while thn 4.1 needs d≥Ω(V)d\geq \Omega\left(\sqrt{V}\right). The paper does not show that this gap is necessary, close to necessary, or associated with an actual optimization barrier. At the moment, this looks more like a technically interesting sufficient condition than a strong explanation of training dynamics.

A1: Thank you for raising this insightful question. We do not view the V\sqrt V threshold as a fundamental optimization barrier. Instead, d=Ω(V)d=\Omega(\sqrt V) is a simple sufficient condition that supports a common analysis for the untied and tied models, and balances generality, practical relevance, and clarity. Specifically,

  • (1) In the analysis, a larger dd provides more embedding directions along which the model can adjust its embeddings. This coincides with many empirical findings that a larger embedding dimension supports better training performance.
  • (2) In practice, the rank rr of the ground truth is typically unknown, whereas the vocabulary size VV is known. Thus, a condition on dd in terms of VV is also informative.
  • (3) Many practical models fall into this regime. For example, Gemma 2 2B uses V=256128V=256128 and d=2304d=2304, which satisfies V<d≪V\sqrt V<d\ll V (Gemma Team, 2024).

In addition, although d≥rd\ge r guarantees that the ground truth is representable, establishing that training leads a useful predictor is substantially more difficult, since both embeddings evolve simultaneously under a nonconvex cross-entropy objective, whose Hessian depends on the learned predictions and can become nearly singular. In the untied model, our analysis can relax d=Ω(V)d=\Omega(\sqrt V). However, the proof is lengthy, introduces extremely large constants, and does not directly extend to tied embeddings. Therefore, relaxing the lower bound on dd in general requires further non-trivial effort.

W2: Scope: the strongest transfer result remains conditional on an important property that training itself does not establish. Thm 5.4 requires centered coverage and uniformly bounded learned rows, and the paper explicitly states that the optimization analysis does not prove the learned-row condition. This makes the transfer result less satisfying as a statement about what the proposed training algorithm actually learns.

A2: Thank you for raising this insightful question. We do not view this condition as fundamental to the transfer through tied embeddings. In fact, our analysis can remove it at the cost of a larger embedding dimension and a weaker rate, or under additional structure on the ground truth. However, the corresponding proofs are lengthy, and removing the condition while keeping the same class of ground truths, the same requirement on the embedding dimension, and the same rate requires further non-trivial analysis. We therefore present the conditional guarantee to balance the generality of the ground truth, the strength of the bound, and clarity.

Specifically, the difficulty in removing this condition is that our optimization analysis controls the total energy ∥X∥F2\|X\|_F^2 of the embeddings, which does not exclude the concentration of the energy on a few embeddings. Such concentration can have a small effect on the training loss on the observed states, while substantially changing the predictions on the unseen states. The bound on the learned embeddings rules this out. It keeps the logits bounded and thus controls the curvature of the softmax, which allows us to translate the bound on the training loss into a bound on the Gram matrix XX⊤XX^\top, and then into the guarantee on the unseen states.

AuthorsOpenReview ↗

Responses to Questions

Q1: Is there any evidence that the d=Ω(V)d=\Omega(\sqrt{V}) scale is intrinsic? For example, can the authors give a lower bound, hard instance, or failure mode below this scale?

A3: Please see our response A1 to W1.

Q2: Can the bounded learned-row assumption in Thm 5.4 be proved from the training dynamics, or substantially weakened?

A4: Please see our response A2 to W2.

Q3: Beyond improving the sufficient width bound, is there a stronger consequence of the trace-based argument that would distinguish a genuine learning phenomenon from proof slack?

A5: The most important consequence of the trace-based argument is a quantitative connection between the prediction quality and the optimization landscape. That is, the local information, i.e., the gradient (first order) and the Hessian (second order), reveals the global information, i.e., the value of the loss, or equivalently, the prediction quality. Specifically, in the region reached by training, every point whose objective is above the level required for gain 7/87/8 must have either a large gradient or a direction of negative curvature (Lemma B.4).

This is relevant to learning, because the generic saddle-escaping analysis only guarantees approximate second-order stationarity, which does not imply useful predictions. Our result supplies this missing implication. Combined with the control on the increase of the objective between consecutive visits to such points, it yields high prediction gain throughout the final window of training.


If our responses and revision have addressed your remaining concerns, we kindly ask you to consider a higher score. We welcome any further questions and thank you again for your time and feedback.

thanks for the clarification. I agree that a sufficient guarantee need not identify a sharp optimization threshold. the trace-based argument and final-window guarantee are genuine contributions, as I noted in my review. however, I am still not convinced that their significance is strong enough to change my assessment. the transfer result also remains conditional on a learned-row bound that the training analysis does not establish. the suggested extensions may help, but without precise statements and proofs, I cannot assess whether they resolve these concerns. I therefore maintain my weak-reject recommendation.

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

This paper investigates how gradient-based learning learns state-transition models using tied and untied input- and output embeddings. Under some assumptions, the authors show that noisy gradient descent with weight decay learns good next-state predictions and maintains them over a long stretch of training. Under additional assumptions, tied embeddings also allow the model to generalize out of its training distribution.

Critical strengths
  • The guarantees cover the training trajectory, not just at initialization.
  • The theoretical framework seems to be consistent.
Critical weaknesses

The paper uses technical language that makes it hard to follow without the necessary mathematical background. While I understand the difficulty of striking the correct balance between taking a reader along without starting from zero. It should provide the reader with an intuition for the method, which it currently does not. Furthermore, the experimental section is very hard to follow (see f.e. the "persistent grain and tied transfer" paragraph).

In its current form, I therefore do not consider the paper ready to be read by a human and tend to recommend rejection.

Questions for authors
  • Would the reader consider making the paper easier to follow, taking along even readers not deeply familiar with the work?
  • Furthermore, the paper would profit from informal statements in the main paper that are formalized in the appendix.
3 comments
AuthorsOpenReview ↗

Responses to Weaknesses and Questions

We thank the reviewer for careful reading and thoughtful comments. We provide detailed responses below.

W1: The paper uses technical language that makes it hard to follow without the necessary mathematical background. While I understand the difficulty of striking the correct balance between taking a reader along without starting from zero. It should provide the reader with an intuition for the method, which it currently does not. Furthermore, the experimental section is very hard to follow (see f.e. the "persistent grain and tied transfer" paragraph).

In its current form, I therefore do not consider the paper ready to be read by a human and tend to recommend rejection.

A1: Thank you for this valuable feedback. We have substantially rewritten the paper in the revision to make it easier to follow. The main changes are summarized below.

  • (1) Introduction. We add Figure 1 to illustrate the performance metric, i.e., the relative prediction gain (RPG).
  • (2) Intuition for the method. Section 4.1 now starts with the high-level idea (lines 251–267), which is illustrated in Figure 2. Intuitively, gradient descent with small perturbations can only stay around points that have a small gradient and no direction of negative curvature, i.e., approximate second-order stationary points. The key of our analysis is to show that every such point reached by training already predicts well. To this end, the weight decay keeps the iterates in a bounded region, in which this property holds. Then, since the objective can only increase slightly between two consecutive visits to such points, the prediction remains accurate throughout the final window of training.
  • (3) Main results and proofs. Each theorem is now followed by a short explanation of what it states. Each proof overview consists of three steps, where each step states what is shown, gives the key inequality, and points to the corresponding lemma in the appendix. The appendix is reorganized to follow the same three steps.

Regarding the paragraph "Persistent gain and tied transfer", it reports three observations, which correspond to our three theorems.

  • (i) The training gain remains high throughout the final window [T/d,T][T/d,T] (Theorems 4.1 and 5.2). The gain stays above 7/87/8 in all 135 runs of the untied model and in 120 of the 135 runs of the tied model. The exceptions are the runs with the smallest embedding dimension (V=64V=64, d=8d=8).
  • (ii) The tied model transfers to unseen states (Theorem 5.4). When both models are trained on the same observed states, the final gain of the tied model on the unseen states is above 0.960.96, while that of the untied model remains near zero.
  • (iii) The condition on the learned embeddings in Theorem 5.4 holds in the experiments. The squared norms of the learned embeddings stay below the bound R0=8R_0=8, which is fixed in advance, in all runs of the tied model.

In the revision, we have reorganized this paragraph along these three observations (lines 473–480).

Q1: Would the reader consider making the paper easier to follow, taking along even readers not deeply familiar with the work?

A2: Yes. Please see our response A1 to W1 for the changes in the revision.

Q2: Furthermore, the paper would profit from informal statements in the main paper that are formalized in the appendix.

A3: Thank you for this suggestion. In the revision, each theorem in the main text is followed by an informal explanation of what it states (e.g., lines 240–242 for Theorem 4.1), and the proof overviews are presented with informal inequalities such as ≲\lesssim. The complete statements with all parameter choices, together with the proofs, are given in Appendices B and C.


If our responses and revision have addressed your remaining concerns, we kindly ask you to consider a higher score. We welcome any further questions and thank you again for your time and feedback.

Thank you for the details response and the effort in improving the papers clarity. I appreciate the added explanations and the structure of the presentation.

I share the concerns about significance. It remains unclear whether the embedding size requirement is due to a limitation of training or the proof. I will therefore maintain my weak-reject recommendation.

I do, however, acknowledge my limited familiarity with the broader literature, which is why I have selected a low confidence.

Thank you for acknowledging the improvements in clarity. We would like to distinguish two aspects of the embedding dimension requirement.

First, d<Vd<V specifies the practically relevant regime. The embeddings are lower-dimensional than the vocabulary. When d≥Vd\ge V, token embeddings can be linearly independent, which removes the representational bottleneck, and is far from real implementation in language models. Our question is whether jointly trained low-dimensional embeddings can learn accurate predictions.

Second, d=Ω(V)d=\Omega(\sqrt V) is a sufficient condition. In fact, our additional analysis can reduce the sufficient width to d=Ω(log⁡V)d=\Omega(\log V) for the untied model. However, this refinement requires a substantially longer proof, introduces potentially enormous constants, and does not directly extend to tied embeddings. We therefore present the square-root condition to balance generality across the two models, practical relevance, and clarity (Please also see our response A1 to reviewer 9cRu).

Whether the requirement can be further reduced to d≥rd\geq r remains open: representability alone does not guarantee successful optimization, and there are also potential optimization barriers at this embedding dimension, i.e. the GD-based method may not converge or not achieve high gain (low loss) at this extreme low dimension regime.

The significance of our result is the theoretical guarantee for practical relevant settings: jointly learned low-dimensional embeddings, random initialized and trained by perturbed GD with weight decay, achieve RPG above 7/87/8 with high probability. Establishing this behavior can be seen as a first step towards understanding the training dynamics of a real transformer model on language tasks.


We thank the reviewer again for the valuable feedback and welcome any further questions and discussions.

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

The paper considers learning a state-transition table QQ using a model of the form softmax(EUT)softmax(EU^T), where both embedding matrices are trained. The main assumption is that the row-centered log-probability table of QQ has fixed low rank and bounded entries. The learning algorithm has access to QQ, applies Gaussian initialization, weight decay and Gaussian perturbations at every update. The main theorem states that, for sufficiently large embedding dimension d≥CVd \geq C\sqrt{V}, with high probability every iterate from T/dT/d to TT achieves relative prediction gain (RPG) above 7/87/8, where RPG is a certain measure of success. There are also results for tied embeddings, i.e. E=UE=U, including a conditional prediction guarantee on unseen input states when only some rows of QQ are used for training. The main proof idea uses the trace of the softmax Hessian to find directions with small curvature, combined with existing results on perturbed GD. The paper contains synthetic experiments with both population gradients and sampled SGD.

Critical strengths
  • The theorems are precisely stated. The proofs are presented in detail in the appendix, and the main steps are explained in Sections 4.1, 5.1.1 and 5.2.1. During the limited time of the review period I could not find any serious mistake in the proof.

  • The learning process does not need good-enough initial estimates (Gaussian initialization is enough) and the prediction guarantee holds for every iterate in a certain final phase of the training, while the perturbations are still present.

  • To me the most interesting proof idea is described in Section 4.1 referring to Lemma B.3, namely finding directions with both small embedding energy and small softmax curvature yield an O(V/d2+1/d)O(V/d^2+1/d) curvature term. The proof uses existing tools, but this particular combination does not seem trivial.

  • The paper establishes a conditional tied transfer bound for predicting unseen input states.

Critical weaknesses
  1. Some closely related literature should be discussed. For squared-loss / Frobenius matrix factorization, there are already GD results from random initialization. The results in e.g. https://proceedings.neurips.cc/paper/2021/hash/0af854284f4ab0cfea8fcfd889cbb41a-Abstract.html. should be discussed and compared to the current results.

There is also relevant recommender-system literature, e.g. https://proceedings.mlr.press/v267/sankagiri25a.html and https://jmlr.org/papers/v19/17-607.html. These should also be cited and potentially compared to the current results.

  1. Is this problem really that well motivated? I am not particularly familiar with the related literature, however to me it seems that the central problem is factorizing a known low rank (at least L(Q)L(Q) is low rank, but in my understanding we can just transform the problem to factorizing a low rank matrix) logit matrix using a very concrete GD variant on the cross-entropy loss.

Why is this problem significant enough, especially considering the literature on SVD and matrix factorization using other GD variants with various loss functions?

  1. Additional assumptions seem also restricting compared to actual learning. The paper assumes exact low-rank logits, bounded logits and a fixed positive lower bound on the information gap logV−H[V]logV - \mathcal{H}_{[V]}. What is the motivation behind this setup? Is this a significant leap compared to where the literature is? I am not really convinced by Technical challenges paragraph at the end of Section 3.

Even in Theorem 5.4 there is max⁡j∣∣xj(t)∣∣≤R0\max_j ||x_j(t)|| \leq R_0 which is an additional condition as the paper rightfully admits (line 329). While it has some experimental support, it is not theoretically guaranteed.

Questions for authors
  1. Please address the mentioned related work and possibly compare and highlight differences and improvements. The difference in the proof techniques would be also nice to see.

  2. Could you explain in more details and more specific citations why this is a well motivated work and not an overly speficic learning problem? Why is this significane enough for publications? Is it a special case of real world applications? If so, how special?

  3. Is the uniform bound assumption in Theorem 5.4 a real obstacle or just a technicality? Can you give some conditions under which the training algorithm guarantees it (maybe with high probability), so that the bounding term is independent of VV?

  4. Do you expect the proof technique to be extendable to more general frameworks and less restrictive assumptions? Maybe learning from state-transition samples instead of access to QQ or L(Q)L(Q)?

7 comments
AuthorsOpenReview ↗

Responses to Weakness 1-2

We thank the reviewer for careful reading and thoughtful comments. We provide detailed responses below.

W1: Some closely related literature should be discussed. For squared-loss / Frobenius matrix factorization, there are already GD results from random initialization. The results in e.g. https://proceedings.neurips.cc/paper/2021/hash/0af854284f4ab0cfea8fcfd889cbb41a-Abstract.html. should be discussed and compared to the current results. There is also relevant recommender-system literature, e.g. https://proceedings.mlr.press/v267/sankagiri25a.html and https://jmlr.org/papers/v19/17-607.html. These should also be cited and potentially compared to the current results.

A1: Thank you for these suggestions. We have cited these works and included the comparisons in the revision (Section 2, lines 107–117).

Ye and Du (2021) establish global convergence of vanilla GD from a small random initialization for the squared loss, when the factor width equals the target rank. Sankagiri et al. (2025) analyze preference learning using projected gradient updates from a warm start. Negahban et al. (2018) provide statistical guarantees for convex multinomial-logit estimators. These works are closely related, but they do not establish our guarantees for jointly training the embeddings under the cross-entropy loss, which is the setting of next-token prediction.

We would like to clarify that our motivation is to develop a foundation for the theory of Transformer training through a tractable next-token prediction setting. We keep jointly trained input and output embeddings, Gaussian initialization, the cross-entropy loss, and weight tying. Therefore, unlike the direct analysis of the squared loss in Ye and Du (2021) and the local restricted-curvature arguments in the recommender-system literature, our proof cannot rely on uniform curvature. The technical obstacle is that the Hessian of the cross-entropy loss depends on the learned predictions and can become nearly singular. Instead, our proof uses the bounded trace of this Hessian to show that the approximate second-order stationary points reached by training have high prediction gain, and then controls the iterates of perturbed gradient descent throughout a final window of training. We explain these differences in Section 2 (lines 116–117) and Appendix B.4 of the revision.

W2: Is this problem really that well motivated? I am not particularly familiar with the related literature, however to me it seems that the central problem is factorizing a known low rank (at least L(Q)L(Q) is low rank, but in my understanding we can just transform the problem to factorizing a low rank matrix) logit matrix using a very concrete GD variant on the cross-entropy loss. Why is this problem significant enough, especially considering the literature on SVD and matrix factorization using other GD variants with various loss functions?

A2: Thank you for raising this important question. Our motivation is to understand a fundamental coupling in next-token prediction (NTP) training: the context representation and the output embeddings are learned simultaneously, and each of them changes the optimization problem faced by the other.

Specifically, the NTP logits take the form hθ(c)⊤ψ(j)h_\theta(c)^\top\psi(j), where cc is the context, hθh_\theta is a neural network, and ψ(j)\psi(j) is the output embedding of token jj. We isolate this coupling through a one-token context, in which hθ(c)h_\theta(c) reduces to the input embedding ϕ(c)\phi(c) of the current token. This removes the attention and MLP layers, while preserving jointly trained embeddings with d<Vd<V, the cross-entropy loss, and optional weight tying. Understanding these components provides a starting point for the theory of Transformer training. Existing NTP analyses consider, for example, fixed context embeddings (Thrampoulidis, 2024) or two-stage training (Huang et al., 2024), and thus do not cover jointly trained embeddings, as discussed in Section 1 and in the paragraph "Next-token prediction" of Section 2 (lines 132–138).

Although SVD can factorize a known logit matrix, it does not establish whether simultaneous gradient updates from random initialization learn a useful predictor under the cross-entropy loss. The difficulty remains substantial: the loss is nonconvex in the embeddings, and its Hessian changes with the learned predictions. Weight tying additionally connects learning a token as an output to predicting from it as an unseen input.

Finally, as clarified in Section 3 (lines 177–180), QQ can be the empirical transition table of a dataset that satisfies our assumptions. In this case, our objective is exactly the full-batch negative log-likelihood, and its gradient can be computed directly from the training samples without explicitly knowing QQ or factorizing L(Q)L(Q).

AuthorsOpenReview ↗

Responses to Weakness 3 and Question 1-2

W3: Additional assumptions seem also restricting compared to actual learning. The paper assumes exact low-rank logits, bounded logits and a fixed positive lower bound on the information gap log⁡V−H[V]\log V - H_{[V]}. What is the motivation behind this setup? Is this a significant leap compared to where the literature is? I am not really convinced by Technical challenges paragraph at the end of Section 3. Even in Theorem 5.4 there is ∥x∥≤R0\|x\|\leq R_0, which is an additional condition as the paper rightfully admits (line 329). While it has some experimental support, it is not theoretically guaranteed.

A3: Thank you for highlighting these assumptions. We provide their motivations below.

Our assumptions are motivated by observations and practices in modern language models.

  • (1) Low-rank structure in the logits of language models has been observed by Golowich et al. (2026).
  • (2) Bounded logits also have a practical precedent: Gemma 2 explicitly bounds its output logits through soft-capping (Gemma Team, 2024).
  • (3) We impose a positive lower bound on the information gap to exclude ground truths that are close to the uniform distribution, for which the uniform prediction is already nearly optimal and the prediction problem becomes nearly trivial.

These assumptions therefore capture meaningful aspects of practical language modeling, while providing a tractable setting for theoretical analysis.

We also note that our setting is more general in several important respects than those considered in existing transformer and matrix-factorization analyses. Prior studies impose assumptions such as orthonormal embeddings and staged training (Huang et al., 2024), zero initialization and separation of learning timescales (Tian et al., 2023), a warm start with projected updates (Sankagiri et al., 2025), or restricted well-conditionedness of the loss (Li et al., 2017). In contrast, our analysis covers simultaneous training of all embeddings with d<Vd<V from standard Gaussian initialization under the cross-entropy loss.

Regarding the technical challenges, we have rewritten this paragraph in the revision (end of Section 3, lines 210–220). In short, there are three difficulties.

  • (i) With d<Vd<V, the logits are parameterized by the product of the input and output embeddings, which makes the optimization nonconvex.
  • (ii) The Hessian of the cross-entropy loss depends on the learned predictions and can become nearly singular. Thus, the arguments based on uniform curvature do not apply.
  • (iii) Gaussian initialization provides no alignment with the ground truth. Thus, local convergence analyses do not apply.

Moreover, the generic saddle-escaping analysis (Jin et al., 2019) only guarantees that the algorithm visits approximate second-order stationary points, which does not imply accurate prediction by itself. Our analysis fills this gap in two steps: (a) we show that every such point in the region reached by training has high prediction gain, and (b) we control the iterates between consecutive visits to such points.

Finally, for the condition max⁡j∥xj∥22≤R0\max_j\|x_j\|_2^2\le R_0 in Theorem 5.4, please see our response A6 to Q3.

Gemma Team (2024), Gemma 2: Improving Open Language Models at a Practical Size

Golowich et al. (2026), Sequences of Logits Reveal the Low Rank Structure of Language Models, ICLR 2026

Huang et al. (2024), Non-asymptotic Convergence of Training Transformers for Next-token Prediction

Tian et al. (2023), Scan and Snap: Understanding Training Dynamics and Token Composition in 1-layer Transformer

Sankagiri et al. (2025), Recommendations with Sparse Comparison Data: Provably Fast Convergence for Nonconvex Matrix Factorization

Li, Zhu & Tang (2017), Geometry of Factored Nuclear Norm Regularization

Jin et al. (2019), On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points

Q1: Please address the mentioned related work and possibly compare and highlight differences and improvements. The difference in the proof techniques would be also nice to see.

A4: Please see our response A1 to W1.

Q2: Could you explain in more details and more specific citations why this is a well motivated work and not an overly specific learning problem? Why is this significane enough for publications? Is it a special case of real world applications? If so, how special?

A5: Please see our responses A2 and A3, which explain the motivation and justify the assumptions. In summary, this problem is motivated by the success of next-token prediction training. It is the special case of NTP with a one-token context, and the model consists of the input and output embeddings, which are part of every language model. We note that this problem is already challenging, and it serves as a starting point for the more complicated training dynamics of transformers.

AuthorsOpenReview ↗

Responses to Question 3-4

Q3: Is the uniform bound assumption in Theorem 5.4 a real obstacle or just a technicality? Can you give some conditions under which the training algorithm guarantees it (maybe with high probability), so that the bounding term is independent of VV?

A6: Thank you for raising this insightful question. We do not view this condition as fundamental to the transfer through tied embeddings. In fact, our analysis can remove it at the cost of a larger embedding dimension and a weaker rate, or under additional structure on the ground truth. However, the corresponding proofs are lengthy, and removing the condition while keeping the same class of ground truths, the same requirement on the embedding dimension, and the same rate requires further non-trivial analysis. We therefore present the conditional guarantee to balance the generality of the ground truth, the strength of the bound, and clarity.

Specifically, the difficulty in removing this condition is that our optimization analysis controls the total energy ∥X∥F2\|X\|_F^2 of the embeddings, which does not exclude the concentration of the energy on a few embeddings. Such concentration can have a small effect on the training loss on the observed states, while substantially changing the predictions on the unseen states. The bound on the learned embeddings rules this out. It keeps the logits bounded and thus controls the curvature of the softmax, which allows us to translate the bound on the training loss into a bound on the Gram matrix XX⊤XX^\top, and then into the guarantee on the unseen states.

Q4: Do you expect the proof technique to be extendable to more general frameworks and less restrictive assumptions? Maybe learning from state-transition samples instead of access to QQ or L(Q)L(Q)?

A7: We believe that the localization argument (Step 1 in Section 4.1) can be extended to models with attention. Specifically, the weight decay makes the objective large whenever the parameter norm is large, and therefore keeps the parameters within a bounded region. Such boundedness then allows us to control the fluctuation of the objective along the trajectory through its gradients. Extending the rest of the analysis requires an attention-specific argument that links approximate stationarity to prediction quality.

For the access to QQ, as discussed in our response A2, our analysis admits a sample-based interpretation: QQ can be the empirical transition table of a dataset that satisfies our assumptions (Section 3, lines 172–175), and the gradient of the cross-entropy loss can be computed directly from the transition samples, without explicitly constructing QQ or L(Q)L(Q). In addition, Section 6.2 reports experiments with SGD on sampled transitions, where high prediction gain is also observed.


If our responses and revision have addressed your remaining concerns, we kindly ask you to consider a higher score. We welcome any further questions and thank you again for your time and feedback.

Comments on the paper

1 comment

Dear Reviewers,

Thank you for your time in evaluating this paper. Since there is only one day left for this stage, could you please read the rebuttal and provide a response? This is important for the review process.

AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.