Oussama Zekri
ENS Paris-Saclay & Imperial College London
28th November 2024, 2:00PM - 3:00PM (GST)
| Title: | Large Language Models as Markov Chains |
| Abstract: | 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 $\cxtsize$ and Markov chains defined on a finite state space of size $\mcal{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. |
| Bio: | Oussama Zekri is a final-year mathematics student at ENS Paris-Saclay and currently an intern at Imperial College London. His research spans applied mathematics and machine learning, with recent work focused on generative models. Oussama has completed internships at Huawei Noah's Ark Lab, Kyoto University's System Optimization Laboratory, and Centre Borelli, ENS Paris-Saclay, contributing to projects on large language models, convex optimization, time series, and optimal transport. He has authored multiple research papers and co-authors a research blog, logB. |