Large Language Models as Markov Chains

• URL: http://arxiv.org/abs/2410.02724v2
• Date: Sun, 02 Feb 2025 15:57:01 GMT
• Title: Large Language Models as Markov Chains
• Authors: Oussama Zekri, Ambroise Odonnat, Abdelhakim Benechehab, Linus Bleistein, Nicolas Boullé, Ievgen Redko,
• Abstract summary: We draw an equivalence between autoregressive transformer-based language models and Markov chains defined on a finite state space. We relate the obtained results to the pathological behavior observed with LLMs. Experiments with the most recent Llama and Gemma herds of models show that our theory correctly captures their behavior in practice.
• Score: 7.078696932669912
• License:
• 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.

Related papers

• Zero-shot Model-based Reinforcement Learning using Large Language Models [12.930241182192988]
  We investigate how pre-trained Large Language Models can be leveraged to predict in context the dynamics of continuous Markov decision processes. We present proof-of-concept applications in two reinforcement learning settings: model-based policy evaluation and data-augmented off-policy reinforcement learning.
  arXiv  Detail & Related papers  (2024-10-15T15:46:53Z)
• Inductive Learning of Logical Theories with LLMs: An Expressivity-Graded Analysis [9.865771016218549]
  This work presents a novel systematic methodology to analyse the capabilities and limitations of Large Language Models (LLMs) The analysis is complexity-graded w.r.t. rule dependency structure, allowing quantification of specific inference challenges on LLM performance.
  arXiv  Detail & Related papers  (2024-08-15T16:41:00Z)
• From Words to Actions: Unveiling the Theoretical Underpinnings of LLM-Driven Autonomous Systems [59.40480894948944]
  Large language model (LLM) empowered agents are able to solve decision-making problems in the physical world. Under this model, the LLM Planner navigates a partially observable Markov decision process (POMDP) by iteratively generating language-based subgoals via prompting. We prove that the pretrained LLM Planner effectively performs Bayesian aggregated imitation learning (BAIL) through in-context learning.
  arXiv  Detail & Related papers  (2024-05-30T09:42:54Z)
• PoLLMgraph: Unraveling Hallucinations in Large Language Models via State Transition Dynamics [51.17512229589]
  PoLLMgraph is a model-based white-box detection and forecasting approach for large language models. We show that hallucination can be effectively detected by analyzing the LLM's internal state transition dynamics. Our work paves a new way for model-based white-box analysis of LLMs, motivating the research community to further explore, understand, and refine the intricate dynamics of LLM behaviors.
  arXiv  Detail & Related papers  (2024-04-06T20:02:20Z)
• Unveiling the Generalization Power of Fine-Tuned Large Language Models [81.70754292058258]
  We investigate whether fine-tuning affects the intrinsic generalization ability intrinsic to Large Language Models (LLMs) Our main findings reveal that models fine-tuned on generation and classification tasks exhibit dissimilar behaviors in generalizing to different domains and tasks. We observe that integrating the in-context learning strategy during fine-tuning on generation tasks can enhance the model's generalization ability.
  arXiv  Detail & Related papers  (2024-03-14T08:18:59Z)
• Characterizing Truthfulness in Large Language Model Generations with Local Intrinsic Dimension [63.330262740414646]
  We study how to characterize and predict the truthfulness of texts generated from large language models (LLMs) We suggest investigating internal activations and quantifying LLM's truthfulness using the local intrinsic dimension (LID) of model activations.
  arXiv  Detail & Related papers  (2024-02-28T04:56:21Z)
• Sparsity-Guided Holistic Explanation for LLMs with Interpretable Inference-Time Intervention [53.896974148579346]
  Large Language Models (LLMs) have achieved unprecedented breakthroughs in various natural language processing domains. The enigmatic black-box'' nature of LLMs remains a significant challenge for interpretability, hampering transparent and accountable applications. We propose a novel methodology anchored in sparsity-guided techniques, aiming to provide a holistic interpretation of LLMs.
  arXiv  Detail & Related papers  (2023-12-22T19:55:58Z)
• Large Language Models Are Latent Variable Models: Explaining and Finding Good Demonstrations for In-Context Learning [104.58874584354787]
  In recent years, pre-trained large language models (LLMs) have demonstrated remarkable efficiency in achieving an inference-time few-shot learning capability known as in-context learning. This study aims to examine the in-context learning phenomenon through a Bayesian lens, viewing real-world LLMs as latent variable models.
  arXiv  Detail & Related papers  (2023-01-27T18:59:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.