acceptodds
Under review as a conference paper at ICLR 2027

Can LLMs Learn to Generalize before Memorizing High-Order Markov Chains?

Abstract

Early stopping is a widely-used implicit regularization technique that halts training before full optimization of training to avoid overfitting. In supervised learning it is an effective safeguard against overfitting, and it has recently been identified as a key ingredient of generalization in diffusion models. We ask whether early stopping can similarly prevent memorization when causal language models are trained on sequences generated by order- Markov chains. Our answer is mixed. For low-order chains, early stopping leads to generalization, but for high-order chains it is not sufficient. Theoretically, we establish a regularization sufficient for learning order- chains, which implicitly holds early in training. Empirically, we find that for high-order chains this implicit regularization vanishes early in training, so stopping fails to prevent memorization.

Primary area:
learning theory
Keywords:
artificial intelligence, machine learning, large language models

Reviews

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

The paper studies whether early stopping lets causal language models learn a Markov transition kernel before memorizing the training data. It finds a generalization window for low-order chains that disappears at higher orders. It connects this behavior to limited context dependence early in training, with an order-1 estimation result and experiments on synthetic chains and text.

Critical strengths

Knowing the true kernel makes this a useful setting for separating kernel recovery from fitting the training sample. I found the disappearing generalization window in Figure 1 interesting, and the distance to context-limited predictor classes is a useful way to investigate it.

Critical weaknesses
  1. I am not convinced that Figure 3b supports the main explanation. The caption says that P5\mathcal P_5 replaces Pk\mathcal P_k for k>5k>5. A small loss reduction within P5\mathcal P_5 does not imply a small reduction within Pk\mathcal P_k: the missing context may contain exactly the structure that needs to be learned. This leaves unclear whether the failure comes from insufficient data or the model’s learning dynamics.

  2. I had trouble following the guarantee in Theorem 2. Even if a state is visited many times, some outgoing transitions may remain unseen, making the KL divergence infinite for the unsmoothed estimator. Remark 3 acknowledges this, so how does the finite expectation bound handle these cases? The proof also assumes multinomial transition counts conditional on visit counts, but those visit counts themselves depend on the transitions. These points need to be resolved for the bound to hold.

Questions for authors
  1. Could you clarify what Figure 3b would show using the actual Pk\mathcal P_k for k>5k>5? In particular, does a smoothed order-kk count estimator generalize on the same datasets where the transformer fails? This comparison would substantially affect my interpretation of the result.

  2. Is Eq. 13 intended as an expectation conditional on a good event, or as a high-probability guarantee? How are zero-count transitions and the dependence between visit counts and transitions handled?

2 comments
Reviewer_kq8KOpenReview ↗

No Response Received

While the other reviewers have received responses, I have not received any response, even after waiting a few more days.

We appreciate the reviewer for their technically deep review and also for their heads up bellow showing their commitment.

While the other reviewers have received responses, I have not received any response, even after waiting a few more days.

We were working on your comment bellow

The proof also assumes multinomial transition counts conditional on visit counts, but those visit counts themselves depend on the transitions. These points need to be resolved for the bound to hold. Is Eq. 13 intended as an expectation conditional on a good event, or as a high-probability guarantee?

It is a high probability statement under a technical condition on \\# a. We were working on Theorem 2 to remove the condition on \\# a to make the statement stronger. While we believe that it is possible to prove the condition on $\# a> ... $ event holds with high probability but, it requires invoking results from Markov chain theory and the statement will depends on the spectral gap of the Markov chain. We were not able to complete the analysis by the rebuttal deadline. Here, we provide our responses to the remaining concerns.

In particular, does a smoothed order-kk count estimator generalize on the same datasets where the transformer fails?

We computed both (Appendix E, Figure 11) where we observed that actually count estimator has less generalization error compared to the trained transformer (see Figure 11). A smoothed order-kk count estimator recovers the kernel up to k=9k = 9, whereas the transformer generalizes only up to k=6k = 6 (Figure 11a). The failure therefore comes from the learning dynamics, not from insufficient data.

A small loss reduction within P5P_5 does not imply a small reduction within PkP_k [...]. Could you clarify what Figure 3b would show using the actual PkP_k for k>5k > 5?

With the exact Pk\mathcal{P}_k, the training-loss reduction remains close to 0.40.4 nats at every order, including k=8k = 8 and 99 (Figure 11b); the decrease observed in Figure 3b is therefore an artifact of substituting P5\mathcal{P}_5. Figure 10 provides an additional result, reporting the distance d(ft,Pk)d(f_t, \mathcal{P}_k) while learning an order-6 Markov chain. We observe that the model leaves the function class P6\mathcal{P}_6 once it begins to memorize. The difficulty is that the model exits all function classes early in training and thus quickly loses the lazy-sensitivity property. This makes generalization challenging for high-order Markov chains.

I had trouble following the guarantee in Theorem 2. Even if a state is visited many times, some outgoing transitions may remain unseen, making the KL divergence infinite for the unsmoothed estimator.

Since the starting is from a uniform random state and transition kernel is alwasy non-zero bound bellow by pmin⁡p_{\min}.

Remark 3 acknowledges this, so how does the finite expectation bound handle these cases?

Remark 3 head up is regarding our data generation mechansim. The condition of p(a∣b)>pminp(a|b)>p_{min} may be violated when we generate a random Dirichlet kernel in our experiments.

The proof also assumes multinomial transition counts conditional on visit counts, but those visit counts themselves depend on the transitions. These points need to be resolved for the bound to hold.

This is by the definition of sum of the appearance of the next variable. Since the next variable is discrete, its count become a multinomial random variable conditioned on the pervious state. The parameters of this multinomial distribution depends on the transition kernel. We later replace the kernel dependency using p(a∣b)>pmin⁡p(a|b)> p_{\min}.

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

This paper asks whether as training progresses, LLMS learn Markov chains of increasing order k or instead learn the empirical distribution over the data. They observe that as training progresses, their models initially appear to be closest to a Markov chain of order k=1, before they progress to higher orders. They prove that a) restricting the model class to k=1 order Markov chain, their training objective reduces to the KL distance between the best k=1 Markov chain describing the data, they then b) give a statement for how this KL divergence diminishes as a function of the number of training data, M.

Critical strengths
  • The authors experiments consistently show a simplicity bias in LLMs and a late onset of memorization
  • The authors show empiricially that with growing k, there is a generalization time \tau_gen that grows with k while the memorization time \tau_mem remains largely unchanged, indicating that with increasing k, no generalization before memorization should be observed
Critical weaknesses
  • There are multiple instances of inconsistencies within the text, the text describing the figures, and the structure of the paper, some of them could be typos, some of them I found misleading. I give a non-exhaustive list of the ones that I caught below. Overall these repeating inconsistencies significantly diminish the reliability of the paper.
  • After reading the paper, it is not clear to me what the novelty is. Simplicity bias in learning generative models is by now well-known and has been theoretically studied, also for LLMs. The main, theoretical contribution appears to be theorem 2, which appears to be known already. The second strength I listed to me promises to be the most constructive direction, but it is shown only for synthetic data in a limited experimental scope, and does not appear to be addressed or even proven by the theory.
Questions for authors
  • Section 4 starts with the following statement: "the constraint f_t in \mathcal{P}_1 turns the training objective into a consistent estimator of p. Figure 1 shows that this phenomenon is absent for large k." Indeed, Theorem 2 shows that given enough training data, f_t in \mathcal{P}_1 eventually recovers the correct k=1 Markov chain. The main ingredient driving the match is therefore the number of training data. Figure 1, instead, shows training trajectories at fixed sample complexity. How does Fig. 1 establish that increasing the number of training data does not improve performance?
  • The distance measure for defined in equation 14, compares a given Markov chain to its closest equivalent within a given class of k-length Markov chain. Even for the very reduced vocabulary size of 3 used here, the numbers of possible chains grows exponentially as 3^k, and correspondingly the number of possible Markov kernels is a 3^k dimensional-function. Finding the closest function over such a huge space in itself should be a hard computational problem? How is this closest Markov kernel is found in practice? -Figure 3 reports values for k>5 which are estimated from a k=5-order Markov chain. This means that the x-axis in this figure is not properly labeled, beyond k=5, the figure measures something else. Why the should the results nevertheless be representative of an order k>5 Markov chain? How do the different values at k>5 even arise, if the reference model is the same?
  • Observation 1 is self-contradictory: The first sentence is that f_t remains inside \mathcal{P}_1, the last sentence states that "it falls outside P_1 ..". The following note justifies the application of the theorem by the observation that f_t is in \mathcal{P}_1. However, it is not clear to me how the theorem is even applied in Fig. 3?
  • Figure 3 reports only the similarity between the trained model f_t and the closest match in \mathcal{P}_1. How does it support the conclusion that f_t is initially closest to P_1 compared to P_k, k>1, as is implied in Observation 2?

Typos/ Notation

  • the marginalized probability of observing a token out of the vocabulary is sometimes called \bar{\mu}, sometimes \mathcal{P}_0
  • The number of training data is referred to as N, except for theorem 2, where it is referred to as M.

Could you comment on your papers contribution in light of this related work? Simplicity bias, beyond the cited references, in Cagnetta et al. NeurIPS 2024. Memorization onset has also been studied extensively in connection to related data properties, see e.g Aparicio Rodriguez et al, ICML 26. In addition to Bonnaire et al., 2025 regarding late onset of memorization in diffusion models, there is also Favero et al., a work with the same central message published at the same conference.

2 comments

Thank you very much for taking the time to review our submission. Based on the reviewers' feedback, we have uploaded a revised version that includes three new subsections in the appendix (highlighted in color).

After reading the paper, it is not clear to me what the novelty is. Simplicity bias in learning generative models is by now well-known and has been theoretically studied, also for LLMs.

We are showing that the simplicity bais vanishes so fast such that it does not help with generalization for high order Markov chains as shown in Figure 1 (compare three rows in Figure 1). Then, we studied why this is the case.

Could you comment on your papers contribution in light of this related work?

  • Bonnaire et al. (2025) is cited in our submission, study the training of diffusion models rather than transformers. Our contribution is to show that the implicit bias of training does not aid generalization for high-order Markov chains. This contrasts with Bonnaire et al. (2025), who argue that early stopping is sufficient to avoid memorization in diffusion models.
  • Cagnetta et al. NeurIPS 2024 studies how LLMs learns grammar from text generated from a context-free grammar. They do not observe or report the challenge of learning high order Markov chains.
  • Aparicio Rodriguez et al, ICML 26: we were not able to find this reference. We only find reference "Concept Reachability in Diffusion Models: Beyond Dataset Constraints" that is presented in ICML 2025 which focus on text-to-image inference time analysis, different from our focus on transformers training.

The main, theoretical contribution appears to be theorem 2, which appears to be known already.

To the best of our knowledge, Theorem 2 is novel: we are not aware of prior results on the constrained function classes Pk\mathcal{P}_k, nor of prior work on training neural networks under this constraint. If the reviewer knows of any relevant references, we would be grateful if they could share them so that we can cite them.

How does Fig. 1 establish that increasing the number of training data does not improve performance?

We repeated the experiment of Figure 1 with N=8N = 8K, 4040K, and 8080K (Appendix D, Figure 8). More data delays τmem\tau_{mem} and moves the horizon from k∗=6k^* = 6 to k∗=8k^* = 8 and beyond k=9k = 9, while τgen\tau_{gen} barely changes. At every NN, however, the generalization window shrinks as kk grows. Moreover, at N=8N = 8K the training sample suffices to estimate the kernel: a smoothed count estimator recovers it up to k=9k = 9, where the transformer fails (Appendix E, Figure 11a). A similar dependence on NN was reported for diffusion models (Bonnaire et al., 2025).

Observation 1 is self-contradictory: The first sentence is that ftf_t remains inside P1\mathcal{P}_1, the last sentence states that "it falls outside P1\mathcal{P}_1 ..". [...] it is not clear to me how the theorem is even applied in Fig. 3?

There is no contradiction here. There are two training phases: (1) when the lazy senstivity holds, hence ftf_t is close to the function class P1\mathcal{P}_1 (2) when the lazy sensitivy does not hold (after memorization time) where ftf_t leaves the function class. Note that the model ftf_t is changing with time tt.

Figure 3 reports values for k>5k>5 which are estimated from a k=5k=5-order Markov chain. [...] How do the different values at k>5k>5 even arise, if the reference model is the same?

This is about results in Figure 3b (not Figure 3a). The reference model is ftf_t changes over time tt. With more iteration a model can transfer between function classes. To further clarify on this concern, we added additional results in Figure 10 (Appendix E) that show the transition more clearly.

How does it support the conclusion that ftf_t is initially closest to P1\mathcal{P}_1 compared to Pk\mathcal{P}_k, k>1k>1?

We added the distances to every class Pj\mathcal{P}_j, j≤kj \le k, for a fixed order k=6k = 6, with the exact Pk\mathcal{P}_k (Appendix E, Figure 10). Since the classes are nested, ft∈P1f_t \in \mathcal{P}_1 implies ft∈Pjf_t \in \mathcal{P}_j for all jj. Early in training, ftf_t is within the threshold of every class; it then leaves all of them within about 100100 steps, without settling in an intermediate class. During the generalizing phase, ftf_t is close to Pk\mathcal{P}_k.

Finding the closest function over such a huge space in itself should be a hard computational problem? How is this closest Markov kernel found in practice?

We discuss our method in Appendix B.3. We would be glad to address any further questions during the author–reviewer discussion period.

I thank the authors for their clarifying statements and additional experiments.

Regarding related work and novelty:

First, the reference I mentioned is poster Nr. 63185 at ICML 2026, with the title: "Diffusion Models Preferentially Memorize Prototypical Examples or: Why Does My Diffusion Model Love Slop?".

Also, while I agree that the data model is different, Cagnetta et al's analysis treats a similar phenomenology.

Overall, as the authors also acknowledge, including a preference for shorter-range dependencies, is well studied in this setting. What the authors have changed is it is defined and measured, namely with regards to Markov chains and membership in P1\mathcal{P}_1.

The additional experiment on the sample complexity shows that the window between the generalization and memorization times grows with the sample complexity. This is reassuring, and shows that given enough data, early stopping can be a useful strategy. The authors however don't really discuss this in the main text, beyond introducing the notation k∗(N)k*(N). Given that one of their central arguments is that above a certain length, early stopping doesn't help, I feel that this point deserves more of a discussion.

I'm not sure how the author's response addresses my concern about Figure 3b: In the main text, they use P5P_{5} as a stand-in for PkP_k. In appendix E, in comparison, specifically figure 11 b, shows that this replacement leads to considerably training-loss reductions. Why does Figure 3b report the stand-in measure and how is this justified?

My concerns about novelty and the discussion of the early-stopping conclusion remain. The inconsistency between Figure 3 and Figure 11 also fails to address my concern about of the soundness of this paper. Under these conditions, I feel that I cannot raise my score.

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

The paper study the question of how generalisation and memorisation time depends on the complexity of the task in LLMs.

The paper trains GPT-2 on sequences from a single random order-k Markov chain (|V| = 3, N = 8K sequences). k allows to tune teh complexity of the task. The work defines a generalization time τ_gen (KL to the true kernel below a threshold) and a memorization time τ_mem (training loss falling below the true kernel’s loss on the training set). As k grows, τ_gen grows steeply while τ_mem barely moves, so beyond k ≈ 8 there is no generalization window and early stopping fails.

For k = 1, the authors argue that early training is confined to order-1 predictors (“lazy sensitivity”). Within that class, the training objective is minimized by the empirical kernel, which converges to the true one at rate 1/M. They measure the distance of the model from order-j predictor classes and repeat the analysis on a Markovified Shakespeare corpus and on Wikipedia.

Critical strengths

The setting is clean and controlled, with the true kernel available.

The distance d(f_t, P_j), interpreted as conditional mutual information, is a nice and cheap diagnostic of how much context the model uses.

The observed staged passage P_0 → P_1 → … → P_k is informative.

The paper is clear.

Critical weaknesses

1)The main result has a simple explanation. An order-k kernel has |V|^k (|V| − 1) parameters, so the number of samples needed to estimate it grows with k. At fixed N, increasing k amounts then makes increase tau_gen. One needs n large enough to learn the rule before overfitting can appear after it; below that threshold the model fits the sample first. This is a quite expected phenomenon. The behaviour in Fig. 1 is then what one expects: τ_gen grows with the complexity of the data, and at fixed N the window closes. The horizon k*(N) should simply scale like log N / log|V|. The authors mention this coverage hypothesis in the limitations but do not test it. The key experiment is missing: a phase diagram in (k, N), and a check of whether k*(N) follows this scaling.

  1. Overfitting is not memorization. Δ_t > 0 means the model fits the empirical conditionals better than the true kernel does, which is overfitting. Memorization in the usual sense means generating training sequences verbatim. Several works make this distinction explicitly: Bonnaire et al. (2025), where the train/test loss gap opens well before memorized samples appear; Tirumala et al. (2022), cited by the authors themselves; Favero et al. (2025); and Carlini et al. (2021) on extraction. The paper should discuss this distinction and ideally measure generative memorization too, for example by sampling from the model and counting long verbatim matches with training sequences.

  2. The role of the network is not studied. A single GPT-2 configuration is used, without positional embeddings and with weight decay 0.1. Width, depth, and regularization likely affect τ_mem (which in diffusion models depends on capacity) and the lazy-sensitivity phase. Understanding how k^*(N) depends on the number of parameters, and the architecture would give a clear and interesting picture.

  3. The theory is weak. Theorem 1 is the standard cross-entropy/KL decomposition. Lemma 1 states that the maximum-likelihood estimate is the empirical counts. Theorem 2 is a standard kernel-estimation rate with a suboptimal p_min factor, which the authors acknowledge. All of it is conditional on lazy sensitivity, which is not derived. It covers only k = 1 and does not explain the horizon, which is the main phenomenon.

Questions for authors

none. See weaknesses above for suggestions.

3 comments

Thank you very much for taking the time to review our submission. Based on the reviewers' feedback, we have uploaded a revised version that includes three new subsections in the appendix (highlighted in color).

  1. The main result has a simple explanation. An order-k kernel has |V|^k (|V| − 1) parameters, so the number of samples needed to estimate it grows with k.

We repeated the experiment of Figure 1 with N=8N = 8K, 4040K, and 8080K (Appendix D, Figure 8). More data delays τmem\tau_{mem} and moves the horizon from k∗=6k^* = 6 to k∗=8k^* = 8 and beyond k=9k = 9, while τgen\tau_{gen} barely changes. At every NN, however, the generalization window shrinks as kk grows. This is due to the fact that τmem\tau_{mem} remains almost flat with kk, while τgen\tau_{gen} grows an exponetial rate with kk. Note that N=80000≫∣V∣k≈20000N =80000 \gg |V|^{k} \approx 20000 as k<10k<10 and ∣V∣=3|V| = 3 .

Overfitting is not memorization.

We argue that overfitting leads to regeneration of training sequences. Check our added result in Appendix C (Figures 6 and 7). We observe that in the memorization phase, the model generate more often sequences observed in the training set.

The role of the network is not studied.

We provided additional results for different network depth, width, batchsize, and stepsize in Appendix D (Figure 9).

Theorem 1 is the standard cross-entropy/KL decomposition.

Theorem 1 is not a standard cross-entropy/KL decomposition, as such the decomposition holds only for the function class P1\mathcal{P}_1. To our knowledge, prior work has not studied the constrained function classes Pk\mathcal{P}_k. If the reviewer is aware of such results, we would be grateful for references and would gladly cite them.

Lemma 1 states that the maximum-likelihood estimate is the empirical counts.

The statement is different: if f∈P1f \in \mathcal{P}_1, then the minimizer can be obtained by the empirical transition frequencies when data is generated by k=1k=1 kernel. Without the constrain f∈P1f \in \mathcal{P}_1, the minimizer is different.

Theorem 2 is a standard kernel-estimation rate with a suboptimal pminp_{min} factor, which the authors acknowledge

We do not acknowledge Theorem 2 is a standard kernel-estimation rate. Theorem 2 is not a standard result since it requires the lazy sensitivity condition. What we acknowledged is the establish estimation rate in Theorem 2 is optimal up to the factor 2/pmin2/p_{min}.

All of it is conditional on lazy sensitivity, which is not derived.

Without this condition, Theorem 1, Lemma 1 and Theorem 2 does not hold in practice. The lazy senstivity is not an assumption to make a weak theory. It is necessary for generalization as the generalization does not hold without lazy sensitivity: see the added experimental result in Appendix E (Figure 11a) showing that the trained transformer has a worst estimate than even the empirical count for a large k.

It covers only k = 1 and does not explain the horizon, which is the main phenomenon.

Please check Appendix B.1 where we provided the extension of all theorems to the general k>1k>1.

Thanks for your reply. I find the additional material interesting and valuable. However, it seems to me that it goes in the direction of my main criticism "One needs N large enough to learn the rule before overfitting can appear after it; below that threshold the model fits the sample first. This is a quite expected phenomenon. The behaviour in Fig. 1 is then what one expects: τ_gen grows with the complexity of the data, and at fixed N the window closes." Can the authors comment on this point? Or do they agree but they believe that a thorough study as they do it is valuable ?

AuthorsOpenReview ↗

The challenge is the memorization time

Thanks for considering our response. It is expected that τgen\tau_{gen} grow at an exponential rate with kk. What is surprising, interesting and challenging is the grow rate of τmem\tau_{mem} is not exponential. Our first hypothesis was τmem\tau_{mem} also scales at an exponential rate with kk, therefore there will always be a phase in training such that early stopping works. This hypothesis was inspired by our study of prior works which shows that the implicit bias of SGD is effective in many different cases. Yet, we found the hypothesis was not true for learning high order chains as the implicit bias of SGD vanishes unexpectedly fast.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.