title: Large Language Models as Markov Chains
summary: Large language models (LLMs) have proven to be remarkably efficient, both
  across a wide range of natural language processing tasks and well beyond them.
  However, a comprehensive theoretical analysis of the origins of their
  impressive performance remains elusive. In this paper, we approach this
  challenging task by drawing an equivalence between generic autoregressive
  language models with vocabulary of size T and context window of size K and
  Markov chains defined on a finite state space of size O(T^K). We
  derive several surprising findings related to the existence of a stationary
  distribution of Markov chains that capture the inference power of LLMs, their
  speed of convergence to it, and the influence of the temperature on the latter.
  We then prove pre-training and in-context generalization bounds and show how
  the drawn equivalence allows us to enrich their interpretation. Finally, we
  illustrate our theoretical guarantees with experiments on several recent LLMs
  to highlight how they capture the behavior observed in practice.
paper_authors._id: 66ffa1073187ada66f619f7d
paper_authors.name: Oussama Zekri
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2024-10-04T20:11:21.857Z
paper_authors._id: 651e90f4b395a05dff63fe9e
paper_authors.avatarUrl: https://cdn-avatars.huggingface.co/v1/production/uploads/651e90f4b395a05dff63fe9e/51g5erCgvJ43szg26EQ_M.png
paper_authors.fullname: Oussama Zekri
paper_authors.type: user
paper_authors.user: Xssama
paper_authors._id: 66ffa1073187ada66f619f7e
paper_authors.name: Ambroise Odonnat
paper_authors.status: extracted_confirmed
paper_authors.statusLastChangedAt: 2024-10-04T08:03:48.194Z
paper_authors._id: 6661f79ac36ae4c83f3213e4
paper_authors.avatarUrl: /avatars/2e48f052fdf37b5b06d101a6a3232eea.svg
paper_authors.fullname: Ambroise Odonnat 
paper_authors.type: user
paper_authors.user: ambroiseodt
paper_authors._id: 66ffa1073187ada66f619f7f
paper_authors.name: Abdelhakim Benechehab
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2024-10-09T09:47:26.103Z
paper_authors._id: 621d59ebd3df05d67132e8d9
paper_authors.avatarUrl: https://cdn-avatars.huggingface.co/v1/production/uploads/621d59ebd3df05d67132e8d9/0gPfPTRKKnz5kq0InTqm5.jpeg
paper_authors.fullname: Abdelhakim Benechehab
paper_authors.type: user
paper_authors.user: abenechehab
paper_authors._id: 66ffa1073187ada66f619f80
paper_authors.name: Linus Bleistein
paper_authors._id: 66ffa1073187ada66f619f81
paper_authors.name: Nicolas Boullé
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2024-10-04T09:02:34.994Z
paper_authors._id: 66717cf956b2f9c4d0db149d
paper_authors.avatarUrl: /avatars/57646a3209c75c4b1ff5f4d24a2b0bba.svg
paper_authors.fullname: Nicolas Boulle
paper_authors.type: user
paper_authors.user: NBoulle
paper_authors._id: 66ffa1073187ada66f619f82
paper_authors.name: Ievgen Redko
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2024-10-04T09:02:36.915Z
paper_authors._id: 643d3c9c043254ce1092d195
paper_authors.avatarUrl: /avatars/d44f504d62888e1e8b58f5723147ae9b.svg
paper_authors.fullname: Ievgen R
paper_authors.type: user
paper_authors.user: ievred
paper_title: Large Language Models as Markov Chains
paper_summary: Large language models (LLMs) have proven to be remarkably efficient, both
  across a wide range of natural language processing tasks and well beyond them.
  However, a comprehensive theoretical analysis of the origins of their
  impressive performance remains elusive. In this paper, we approach this
  challenging task by drawing an equivalence between generic autoregressive
  language models with vocabulary of size T and context window of size K and
  Markov chains defined on a finite state space of size O(T^K). We
  derive several surprising findings related to the existence of a stationary
  distribution of Markov chains that capture the inference power of LLMs, their
  speed of convergence to it, and the influence of the temperature on the latter.
  We then prove pre-training and in-context generalization bounds and show how
  the drawn equivalence allows us to enrich their interpretation. Finally, we
  illustrate our theoretical guarantees with experiments on several recent LLMs
  to highlight how they capture the behavior observed in practice.
paper_ai_keywords: autoregressive language models Markov chains stationary distribution speed of convergence temperature pre-training in-context generalization bounds