HackerPapers

arXiv:2410.02724stat.ML

Large Language Models as Markov Chains

Oussama Zekri, Ambroise Odonnat, Abdelhakim Benechehab, Linus Bleistein, Nicolas Boullé, Ievgen Redko

Abstract

Large language models (LLMs) are remarkably efficient across a wide range of natural language processing tasks and well beyond them. However, a comprehensive theoretical analysis of the LLMs' generalization capabilities remains elusive. In our paper, we approach this task by drawing an equivalence between autoregressive transformer-based language models and Markov chains defined on a finite state space. This allows us to study the multi-step inference mechanism of LLMs from first principles. We relate the obtained results to the pathological behavior observed with LLMs such as repetitions and incoherent replies with high temperature. Finally, we leverage the proposed formalization to derive pre-training and in-context learning generalization bounds for LLMs under realistic data and model assumptions. Experiments with the most recent Llama and Gemma herds of models show that our theory correctly captures their behavior in practice.

arXiv comments
Journal reference
DOI
Subjects
stat.MLMachine Learning (Statistics) cs.AIArtificial Intelligence cs.CLComputation and Language cs.LGMachine Learning

On Hacker News

Linked by 8 identifiable commenters in 11 comments across 10 threads, from Jul 2025 to Sep 2026. Found in 3 HN submissions from Oct 2024 to Nov 2024. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments10 threads

  1. The Emergent Symbolic Structure of Artificial Neural Networks 1 comment

    • No misunderstanding at all. "In machine learning, the term stochastic parrot is a metaphor that frames large language models as systems that statistically mimic text without real understanding." https://en.wikipedia.org/wiki/Stochastic_parrot "Large Language Models as Markov…

      chrisjjView on HNParent context

  2. How LLMs work 1 comment

    • No, not nonsense. Both are a lookup table whose key is the entire context window and whose value is a probability distribution for what the next token should be. You can say the choice of probability distribution in the value is "leveraging the internal structure of the context"…

      BorealidView on HNParent context

  3. Transformers are inherently succinct 1 comment

    • > doesn't that mean we're approaching optimality? No. Transformers are Markov chains [1]. Somewhere around this fascinating site [2] I read that stateful models have an advantage. Author provided an example, a state machine with two states A and B, where at state A transitions…

      theszView on HNParent context

  4. Why AI Agents Cannot Change Software Systems 1 comment

    • LLMs are Markov Chains [1]. "Emergent abilities" of LLMs can be explained by decrease of perplexity in text prediction [2]. [1] https://arxiv.org/abs/2410.02724 [2] https://arxiv.org/abs/2304.15004

      theszView on HNParent context

  5. Reflections on AI at the End of 2025 1 comment

    • Regarding the stochastic parrots: It is easy to see that LLMs exclusively parrot by asking them about current political topics [1], because they cannot plagiarize settled history from Wikipedia and Britannica. But of course there also is the equivalence between LLMs and Markov…

      bgwalterView on HNParent context

  6. Ask HN: How are Markov chains so different from tiny LLMs? 1 comment

    • Not that different. In fact, you can use Markov Chain theory as an analytical tool to study LLMs: https://arxiv.org/abs/2410.02724 You could probably point your code to Google Books N-grams (https://storage.googleapis.com/books/ngrams/books/datasetsv3...) and get something that…

      Anon84View on HNParent context

  7. AI is a front for consolidation of resources and power 1 comment

    • If you want to steal code, you can take it from GitHub and strip the license. That is what the Markov chains (https://arxiv.org/abs/2410.02724) do. It's a code laundering machine. Software engineering has a higher number of people who have never created anything by themselves…

      bgwalterView on HNParent context

  8. BERT is just a single text diffusion step 1 comment

    • At no point have I argued that LLMs aren’t autoregressive, I am merely talking about LLMs ability to reason across time steps, so it seems we are talking past each other which won’t lead anywhere. And yes, LLM can be studied under the lens of Markov processes…

      sailingparrotView on HNParent context

  9. The wall confronting large language models 2 comments

    • There definitely is, but Marcus is not the only one talking about it. For example, we covered this paper in one of our internal journal clubs a few weeks ago: https://arxiv.org/abs/2410.02724

      Anon84View on HNParent context

    • Calf isn't making an appeal to authority. They are saying "I'm not the idiot you think I am." Two very different things. Likely also a request to talk more mathy to them. I read your link btw and I just don't know how someone can do all that work and not establish the Markov…

      godelskiView on HNParent context

  10. Problem solving using Markov chains (2007) [pdf] 1 comment

    • > LLMs are Markov Chains on steroids? Might be a reference to this[1] blog post which was posted here[2] a year ago. There has also been some academic work linking the two, like this[3] paper. [1]: https://elijahpotter.dev/articles/markov_chains_are_the_orig... [2]…

      magicalhippoView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.