Large Language Models as Markov Chains

This academic paper explores the theoretical underpinnings of large language models (LLMs), particularly their generalization abilities. The authors propose an equivalence between autoregressive transformer-based LLMs and finite-state Markov chains as a framework for analysis. They use this framework to examine LLM inference, generalization during pre-training on dependent data, and in-context learning on Markov chains, deriving sample complexity and generalization bounds. Experimental results using Llama and Gemma models are presented to validate the theoretical findings, demonstrating how the proposed theory can explain observed LLM behaviors like repetitions and generalize to learning different types of data sequences.