Large Language Models as Markov Chains
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.
66ffa1073187ada66f619f7d
Oussama Zekri
claimed_verified
2024-10-04T20:11:21.857Z
651e90f4b395a05dff63fe9e
https://cdn-avatars.huggingface.co/v1/production/uploads/651e90f4b395a05dff63fe9e/51g5erCgvJ43szg26EQ_M.png
Oussama Zekri
user
Xssama
66ffa1073187ada66f619f7e
Ambroise Odonnat
extracted_confirmed
2024-10-04T08:03:48.194Z
6661f79ac36ae4c83f3213e4
/avatars/2e48f052fdf37b5b06d101a6a3232eea.svg
Ambroise Odonnat 
user
ambroiseodt
66ffa1073187ada66f619f7f
Abdelhakim Benechehab
admin_assigned
2024-10-09T09:47:26.103Z
621d59ebd3df05d67132e8d9
https://cdn-avatars.huggingface.co/v1/production/uploads/621d59ebd3df05d67132e8d9/0gPfPTRKKnz5kq0InTqm5.jpeg
Abdelhakim Benechehab
user
abenechehab
66ffa1073187ada66f619f80
Linus Bleistein
66ffa1073187ada66f619f81
Nicolas Boullé
claimed_verified
2024-10-04T09:02:34.994Z
66717cf956b2f9c4d0db149d
/avatars/57646a3209c75c4b1ff5f4d24a2b0bba.svg
Nicolas Boulle
user
NBoulle
66ffa1073187ada66f619f82
Ievgen Redko
claimed_verified
2024-10-04T09:02:36.915Z
643d3c9c043254ce1092d195
/avatars/d44f504d62888e1e8b58f5723147ae9b.svg
Ievgen R
user
ievred
Large Language Models as Markov Chains
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.
Theoretical analysis of large language models explores their inference capabilities and generalization through equivalence with Markov chains, providing pre-training and in-context bounds.
autoregressive language models Markov chains stationary distribution speed of convergence temperature pre-training in-context generalization