- 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
-
I am not convinced that Figure 3b supports the main explanation. The caption says that replaces for . A small loss reduction within does not imply a small reduction within : 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.
-
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
-
Could you clarify what Figure 3b would show using the actual for ? In particular, does a smoothed order- count estimator generalize on the same datasets where the transformer fails? This comparison would substantially affect my interpretation of the result.
-
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
Rebuttal
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- 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- count estimator recovers the kernel up to , whereas the transformer generalizes only up to (Figure 11a). The failure therefore comes from the learning dynamics, not from insufficient data.
A small loss reduction within does not imply a small reduction within [...]. Could you clarify what Figure 3b would show using the actual for ?
With the exact , the training-loss reduction remains close to nats at every order, including and (Figure 11b); the decrease observed in Figure 3b is therefore an artifact of substituting . Figure 10 provides an additional result, reporting the distance while learning an order-6 Markov chain. We observe that the model leaves the function class 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 .
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 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 .
No Response Received
While the other reviewers have received responses, I have not received any response, even after waiting a few more days.