Large Language Models as Markov Chains

We thank the reviewer Gi2N for their thoughtful feedback. We are happy that the reviewer acknowledged our theoretical results and found our approach unique and the paper well-written.

We address the reviewer's comments point by point below.

1. As noted above, while modeling LLMs as a Markov chain provides a new perspective, there is no new development in Markov chain theory itself. The author's theoretical framework is limited to an extension of existing Markov chain theory, and it remains unclear to what extent this framework fully captures the complex structure and dynamic properties unique to LLMs. Due to the multilayered structure and self-attention mechanisms within LLMs, it is unclear to what extent these can be accurately presented using Markov chains.

We believe there might have been a misunderstanding and would like to clarify that our theoretical analysis focuses on transformer-based architectures: the fixed context window $K$ only characterizes transformer-based LLM architecture. Moreover, the class $\mathcal{F}$, defined right before Section 4.1, is a class of transformer models. In conclusion, our theoretical contribution explicitly relies on the transformer architecture and we believe our results can be highly relevant to the LLM community (being also validated by experiments on commonly used LLMs).

Kindly note that the framework from Section 3 does fully capture the inference mechanism of an LLM, especially its dynamic generation. One simple way to understand why it can be captured explicitly is to recall that the finiteness of the vocabulary and context window allows us to enumerate all possible transitions that an LLM can make. The probabilities of such transitions are estimated by an LLM of choice then define the transition kernel. We would also like to stress out that Section 4 does consider a multi-layered transformer with self-attention mechanism. Hence the proofs extensively rely on the characteristics of the LLM's Transformer architecture and are not a simple extension of Markov chain theory (cf Appendix and proofs p.22-37).

2. The effect of temperature parameters on convergence rate is analyzed, but the influence of other hyperparameters and model structure, such as depth, number of heads, and layer-specific settings, on convergence and inference performance, is not examined in detail. Consequently, the paper provides insufficient guidance for optimal parameter design in LLMs.

Kindly note that Section 3 is concerned only with understanding and characterizing the inference mechanism of the LLMs, while other dependencies are analyzed later in Section 4. Our Theorem 4.1 and Corollary 4.2 show how the pretraining success depends on the number of heads, hidden dimensionality of attention, and MLPs, as well as the boundness of certain weight matrices, and therefore may be of interest for the practical architecture design of LLMs. The experimental results of Section 5 on state-of-the-art also show the high relevance of our theoretical analysis to the LLM community.

3. I believe that Fig.3(d) on line 243 might be a typo for Fig.3(c). Setting that aside, what is the meaning of Fig.3(c)? If the parameter $K$ is only assigned to Llama and GPT, there seems to be no additional information added to Proposition 3.3. Could the authors explain how to evaluate the specific value of $\varepsilon$ in LLMs?

We thank the reviewer for noting this typo and corrected in the revised version of the paper.

This plot shows how the convergence to the stationary distribution depends on the context window size $K$. Intuitively, and as established formally by our theory, for larger $K$, the model has more possible transitions to cover before reaching the stationary distribution. This plot illustrates this behavior for different LLMs based on the value of $K$ and empirically validates our theory (Proposition 3.3). Does this explanation clarify the meaning of Figure 3. c)?

The $\varepsilon$ was fixed to $1e-6$ value for all models as it is impossible to know the lowest probability that a given LLM may assign in principle for a pair of sequences.

Could the reviewer specify what they mean by "$K$ is only assigned to Llama and GPT"? It is also a parameter characterizing our toy model where it is equal to $K=3$ (toy model defined in Section 3.2).

4. Fig.4(d) presents the temperature dependence of $\varepsilon$, but how was this obtained? I may have missed something, but I would appreciate clarification from the authors. It is obvious that convergence is faster at high temperatures, so I am curious about the functional form of $\varepsilon(T)$.

This was obtained from a toy model (defined in Section 3.2) by calculating the min value of the transition kernel (i.e., $\varepsilon$) for different temperatures $\tau$.

We thank the reviewer for their time, their nice words about our work, and for raising their score. This kind of feedback feels encouraging!

Significance of Figure 3(c)

We are happy to have clarified the reviewer's concern. Indeed, in this particular case, we only use the context length of the respective actual models to obtain the plot. However, this experiment can be closely related to several safety issues commonly observed with LLMs. For instance, repetitions and loops in LLM generations connect nicely to the notion of the stationary distribution as looping over the repeating sequences in an almost deterministic way is close to how we interpret the convergence to the stationary distribution in our work. Similarly, recent work showed that almost all LLMs learn a feature that captures the relative frequencies of tokens seen during pretraining [1]. Our work (in particular Proposition 3.3) can hint at the fact that this feature should become increasingly used when the generation goes on for a certain number of steps. In parallel, glitch tokens [2] with low relative frequency may force the LLM to converge to the stationary distribution faster as they increase the value of $\varepsilon$. Other fallbacks of LLM, such as repetitions, are also of great interest [3] and could be analyzed using the Markov chain formalization we propose. We hope that these ideas will be explored by the subsequent works if our paper, acting as a first step in this direction, gets a chance to be published.

Updated Figure 5

We are happy to read that the reviewer appreciates our updated figure. We agree with them that it better shows the rate $\sqrt{\frac{t_{min}}{N_{icl}}}$ from Theorem 4.4. Hence, the reviewer's suggestion of multiplying the vertical axis is (again) excellent as, according to Theorem 4.4, data should collapse onto an approximately universal function.

We thank again the reviewer for their time and precious feedback to improve the paper. If the reviewer thinks our paper sheds new light on important phenomena observed in recent LLMs, we would greatly appreciate their stronger endorsement of our work.

[1] Sean Ogier. LLMs Universally Learn a Feature Representing Token Frequency / Rarity. 2024.

[2] Martin Fell. A Search for More ChatGPT / GPT-3.5 / GPT-4 "Unspeakable" Glitch Tokens. 2023.

[3] Ivgi et al. From Loops to Oops: Fallback Behaviors of Language Models Under Uncertainty. arXiv 2024

We thank the reviewer ugPy for their valuable comments. We are happy to hear that the reviewer found the paper well-written and our theoretical results solid and interesting.

We address the reviewer's concerns point by point below.

1. My main concern is that it is not clear to me what is the connection between the first part (equivalence between autoregressive models and Markov chains) and the second part (generalization bounds) of the paper. As it is, the paper looks like two different papers glued together.

We apologize for the confusion and are happy to provide clarification concerning the two parts of the paper. As noted by the reviewer, the first part establishes an equivalence between LLMs and Markov chains acting on sequences (the mentions of autoregressive models were removed following the Reviewer o34n suggestions), while the generalization bounds rely on the Markov chain viewpoint. Following the reviewer's comment, we revised the paper in Section 4 (l311 & l314), to highlight the dependence of the risk definition on the Markov chain formalization. Finally, our experiments conducted in Section 5, show that our theoretical results, based on the Markov chain framework, are validated on state-of-the-art LLMs.

To further clarify the connections between Sections 3 and 4, we propose to the Reviewer to move the presentation of the sample complexity results given by Corollary 4.3 at the beginning of Section 4. We would then unroll the results that led to it. Would such a transition make the link between the two sections clearer?

2. I struggle to understand the implication of the results of the first part for LLMs. In particular, what does it mean for LLMs to converge to their stationary distribution? Does that mean that the model's loss has converged to some minima? Does that mean that the LLM inference performance cannot be improved further?

On a high level, it means that calling an LLM on any given prompt for a sufficiently (and very large) number of times will lead to a sequence that reflects the frequencies of transitions between different sequences that the LLMs were trained on, regardless of the input prompt. For instance, if in English the token corresponding to the letter $J$ (assuming per letter tokenization for simplicity) has a very low probability to be followed with an $N$ then, and despite the actual context of the appearance of the latter $J$, the LLM will attribute a low probability to $N$ as it has seen few such transitions in the training corpora. One can see this as a universal vocabulary of the rareness of transitions that the LLM's generation converges to, not immediately related to the training process.

3. I was curious about the choice of the TV distance in the risk definition (2). Would it be easy to move to some more popular loss choice for LLMs such as the cross-entropy loss? Intuitively, it shouldn't be too hard since cross-entropy loss is basically KL divergence, which in turn is connected to TV distance through Pinsker's inequality.

We thank the reviewer for suggesting to use the cross-entropy (or equivalently the KL divergence). This intuition of the reviewer is correct as Theorem 4.1, Corollary 4.2, and Corollary 4.3 can be derived too by using the KL divergence instead of the TV distance in the definition of the risk (Eq. 2). Formally, the important sub-result to obtain is akin to Lemma D.6 but with the KL divergence. Assuming that $|\log(\frac{P(z)}{Q(z)})| \leq B$, Lemma D.6 ensures that $d_{TV}(P, Q) \leq \sqrt{2B}$. Similarly, we can show that under the same assumption, we have $d_{KL}(P, Q) \leq B$ and Theorem 4.1, Corollary 4.2 and Corollary 4.3 will follow accordingly by replacing $\sqrt{2B}$ by $B$. Indeed, we have: $0 \leq d_{KL}(P, Q) = |d_{KL}(P, Q)| = |\int P(z) \log(\frac{P(z)}{Q(z)})dz| \leq \int |P(z)| |\log(\frac{P(z)}{Q(z)})|dz.$ As $P$ is a probability distribution, we have $\int |P(z)| dz = \int P(z) dz = 1$ and using $|\log(\frac{P(z)}{Q(z)})| \leq B$, we obtain $d_{KL}(P, Q) \leq B$, which concludes the proof. However, as the KL divergence is not a distance, Theorem 4.4 cannot be obtained as it relies on the triangular inequality. As Theorem 4.4 is one of our main results and enables us to show that our theory aligns with the practice on commonly used LLMs, and that the TV distance is commonly used to compare probability distributions, this motivated us to prefer the TV distance to the KL divergence (or cross-entropy). It should be noted that in our case, Pinsker's inequality is not in the good sense so we cannot use it in our proof. We added these results in the revised paper (Appendix F) and thank again the reviewer for the suggestion.

We hope that all the reviewer's concerns and questions have been addressed. We will be happy to answer any additional questions. Given our explanations and revision to the paper, we would be grateful if the reviewer could reconsider the evaluation of our work accordingly.

I thank the authors for their thorough answers. I increased my score to 6.

We thank the reviewer o34N for their detailed feedback. We appreciate that the reviewer found our work theoretically solid and well-written.

We address the reviewer's concerns point by point below.

1. The reviewer believes that this result adapt previous results by many other learning theory researchers who develop theory on estimating the transition kernel of MC given single path observations.

We believe that there might have been a misunderstanding regarding the scope of our work. While it is true that our theoretical results leverage the classical learning theoretic framework, our work provides a modelization and guarantees on the inference mechanism of LLMs (defined as in the general reply above). These LLMs' generalization bounds are novel in the literature to the best of our knowledge. We revised the paper to include a definition of what we call an LLM in Section 1 (see revised paper l112-116).

As for the results regarding the estimation of the transition kernel of MC given single path observations, we only use them as a baseline in the analysis of Corollary 4.3 to compare the LLM's performance to a frequentist approach but the proofs of Section 3 and 4 do not rely on it.

While leveraging prior work, our proof techniques go well beyond simple and straightforward adaptions (cf. the appendix and proofs p.21-36).

2. The major weakness is the connection to LLMs. The first thing is whether the class F is sufficiently large to include some instances of LLMs.

We employ the term LLM to define a deep transformer-based model trained on non-iid data whose inference is based on the next-token prediction principle. The latter implies that such a model transitions as a Markov chain from a sequence of tokens to a sequence of tokens (with appending and deletion of tokens due to the limited context length). Such a definition includes many, if not all, popular LLMs. We hope that this clarification, along with the empirical results validating our theory on existing modern LLMs, makes the scope of our work clearer to the reviewer.

3. Right now it seems only takes a single input $v_I$ instead of $v_{I-1}, \ldots, v_{I-k}$. Though it may not be feasible anymore to learn MC due to the Markovian properties after we make this change. However, real world language might not be treated as Markovian, which is a very stylized assumption here. The reviewer believes this will affect the impact of this work in the LLM community.

We believe that there might have been a misunderstanding with our theoretical contributions. Here, the input $v_I$ designs a sequence of token (e.g., "I am a "), while the output $v_{I+1}$ is the concatenation of $v_I$ and a token $v$ predicted by the LLM (e.g., "I am a cat"). We note that this does not rely on any Markovian assumption of the language and corresponds to the practical setup used in the LLM community. Following the reviewer's comment, we revised the paper to clarify this point in the introduction after the summary of contributions (see revised paper l112-117).

4. Another huge concern is that $F$ is regardless of the structure of the model itself. It can either be an RNN, Transformer, or a LSTM, and the result continues to hold. It can even be non-NN model. This does not actually reveal why LLM is a powerful machine since it highly depends on the NN as its backbone. Therefore these limitations significantly affect its contribution to the modern LLM theory community.

We believe that there might have been a misunderstanding as we only analyze models with fixed context windows. Although the fixed vocabulary size is common to all these models for language modeling, the fixed context window $K$ only characterizes transformer-based LLM architecture. Hence, other models such as RNNs, LSTMs, or even State-Spaces models (SSMs) like Mamba [1,2] do not fit into our theoretical framework since the context window is only implicit (as it depends on the model's ability to “remember” information about several successive states). Moreover, the class $\mathcal{F}$, defined right before Section 4.1 (l320-331 and Appendix B), is a class of transformer models (therefore a neural network). Finally, our theoretical contribution explicitly relies on the transformer architecture and we believe this makes our results highly relevant to the LLM community (while being also validated by experiments on commonly used LLMs like Mistral 7B, Llama 2, Llama 3.2, Gemma 2B).

[1] Gu and Dao. Mamba: Linear-Time Sequence Modeling with Selective State Spaces. Arxiv 2023.

[2] Dao and Gu. Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality. ICML 2024.

We thank the authors for their clarification on the notations and improved presentations. However, the reviewer is still not convinced that such function class is specific to Transformers. In particular, this does not fully leverage the attention+MLP structure of the Transformers. Given the definition in line 324, the reviewer believes that ML researchers can actually construct so many models that are not Transformers but still satisfy the conditions given by the LLMs in this work. However these models might be very bad in practice and LLMs won't succeed on them while the theoretical results remain untouched (In particular the reviewer thinks that LSTMs and RNNs does not necessarily take the input as a whole and can perform exactly the same as Transformer here). I also checked the proof and realized that the Transformer architecture is not necessary in the proof either.

Hence, using LLM in the title without analyzing the Transformer specific properties might not be very helpful as contributions to the LLM community. The reviewer believes that this is a significant reason that maybe LLM should be removed from the title here. However, as a pure learning theory paper this work seems to also lack theoretical novelties (like solving some novel mathematical open problems and unusual mathematical techniques). The proof idea seems to be quite standard in the literature or the author does not highlight it in the contribution.

Given that the other reviewers remain mildly negative on the acceptance of this work, the reviewer changes the score from 5 to 3 to clarify their stance. However, the reviewer believes that this work might be interesting ( suppose enough technical innovations are made ) to the learning theory community with the removal of LLMs but some class of autoregressive models as the subject of study. Though, in this case, significant contributions in the technical ideas might need to be highlighted.

We thank the reviewer again for their detailed feedback and the time taken to review our work. However, we believe some of the reviewer comments are based on misunderstandings or inaccuracies. Below, we provide a point-by-point response to their concerns, citing specific parts of the paper to address them comprehensively. After addressing these points in detail, we provide a general comment regarding the change in score.

1. Specificity of the function class to Transformers

"The reviewer is still not convinced that such function class is specific to Transformers. In particular, this does not fully leverage the attention+MLP structure of the Transformers."

This statement does not align with the definitions and analysis presented in our paper. Specifically:

• Definition of the class $\mathcal{F}$:
  As defined in Section 4.1 (lines 324–333) and elaborated in Appendix B (pages 16-18), the function class $\mathcal{F}$ is explicitly defined as a class of transformer models. In particular, this section describes that the architecture considered is composed of :

_ Token embeddings.

_ Positional embeddings.

_ Multi-head attention (MHA), followed by a layer normalization.

_ Feed-forward block (with MLP), followed by a layer normalization.

_ Softmax output layer.

• Link to what we have in practice:

We further add that if the reviewer remains unconvinced about the strong connection between our theoretical framework and what an LLM might look like in practice, they could refer to the implementation of an LLM class in the Python transformers package to verify that our modeling aligns closely with the practical architectures used in state-of-the-art systems. For example, the following three lines of code illustrate the architecture of a typical transformer-based LLM (gpt2):

from transformers import AutoModelForCausalLM

model = AutoModelForCausalLM.from_pretrained("gpt2")
print(model)

This outputs:

GPT2LMHeadModel(
  (transformer): GPT2Model(
    (wte): Embedding(50257, 768)
    (wpe): Embedding(1024, 768)
    (drop): Dropout(p=0.1, inplace=False)
    (h): ModuleList(
      (0-11): 12 x GPT2Block(
        (ln_1): LayerNorm((768,), eps=1e-05, elementwise_affine=True)
        (attn): GPT2SdpaAttention(
          (c_attn): Conv1D()
          (c_proj): Conv1D()
          (attn_dropout): Dropout(p=0.1, inplace=False)
          (resid_dropout): Dropout(p=0.1, inplace=False)
        )
        (ln_2): LayerNorm((768,), eps=1e-05, elementwise_affine=True)
        (mlp): GPT2MLP(
          (c_fc): Conv1D()
          (c_proj): Conv1D()
          (act): NewGELUActivation()
          (dropout): Dropout(p=0.1, inplace=False)
        )
      )
    )
    (ln_f): LayerNorm((768,), eps=1e-05, elementwise_affine=True)
  )
  (lm_head): Linear(in_features=768, out_features=50257, bias=False)
)

The architecture includes the following components, which reflect the descriptions in Section 4.1 (lines 320–331) and Appendix B of our paper:

_ Token embeddings: Implemented within (wte).

_ Positional embeddings: Implemented within (wpe).

_ Multi-head attention (MHA), followed by a layer normalization: Implemented within the Attention block (attn), and layer normlization (ln_2).

_ Feed-forward block (with MLP), followed by a layer normalization: Implemented within the MLP module (mlp), and layer normlization (ln_f).

_ Softmax output layer: While not explicitly present in the model architecture, the softmax operation is applied to the logits generated by (lm_head) to obtain probabilities during inference.

This implementation demonstrates that our modelization aligns closely with the practical architectures used in so-called LLMs.

5. Theoretical novelty

"The proof idea seems to be quite standard in the literature or the author does not highlight it in the contribution."

While we utilize classical tools, such as uniform concentration bounds, our work combines these with novel applications tailored to LLMs.

Note that we do not claim to reinvent the foundations of machine learning theory. It is entirely standard to use concentration inequalities to derive generalization bounds. The challenge lies in incorporating the specific characteristics of the model under consideration into the proofs.

We believe we have successfully addressed this challenge in our paper and have clarified our theoretical contributions —particularly that these bounds are explicitly derived for transformer-based LLMs— in the previous points of this answer.

General Comment on the Score Change

We note that you have changed your score from 5 to 3. While we respect your decision, we wish to highlight that:

1. Inconsistency with previous comments: You initially acknowledged that our work is well-written and rigorous. Given the additional clarifications and revisions we have provided, a decrease in score seems difficult to reconcile with your earlier evaluation.

2. Failure to address our clarifications: We have carefully addressed all your feedback, and responded point by point to all your criticisms, both in our initial responses and in the revised manuscript. However, your latest comment ignores many of these clarifications.

3. Experimental contributions ignored: The reviewer mentions that our work is purely theoretical, yet disregards our experimental section, which is based on commonly used LLMs. In addition, it appears that the reviewer undervalues theoretical work within the LLM community, while we believe that such work holds significant value. Moreover, our paper combines both theoretical and experimental contributions, making this critique seem unjustified.

4. Relevance to the LLM community: We do believe that simply stating "I don’t think it is relevant to the LLM community" without engaging with or acknowledging the major contributions we have outlined is not a sufficient basis to lower the score to 3. Our contributions are theoretical and empirical, tailored specifically to transformer-based LLMs, and are clearly detailed throughout the paper. In addition, note that getting theoretical bounds justifying in-context learning capabilities and scaling laws (observed in papers like [1]) was an open problem in the literature.

5. Impact on the review process: Lowering the score after significant revisions and clarifications signals that such efforts are not valued, which may discourage constructive dialogue in future review processes.

We hope this response clarifies any remaining misunderstandings and provides sufficient justification for our work’s contributions to the LLM community. We thank you again for your feedback and your time.

[1] Large Language Models Are Zero-Shot Time Series Forecasters. Gruver et al. NeurIPS 2023