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.<n>We relate the obtained results to the pathological behavior observed with LLMs.<n> 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: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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)
• Thought-Like-Pro: Enhancing Reasoning of Large Language Models through Self-Driven Prolog-based Chain-of-Thought [31.964412924094656]
  Large language models (LLMs) have shown exceptional performance as general-purpose assistants. We introduce a novel learning framework, THOUGHT-LIKE-PRO, to facilitate learning and generalization across diverse reasoning tasks. Our empirical findings indicate that our proposed approach substantially enhances the reasoning abilities of LLMs.
  arXiv  Detail & Related papers  (2024-07-18T18:52:10Z)
• 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)
• Quantifying Emergence in Large Language Models [31.608080868988825]
  We propose a quantifiable solution for estimating emergence of LLMs. Inspired by emergentism in dynamics, we quantify the strength of emergence by comparing the entropy reduction of the macroscopic (semantic) level with that of the microscopic (token) level. Our method demonstrates consistent behaviors across a suite of LMs under both in-context learning (ICL) and natural sentences.
  arXiv  Detail & Related papers  (2024-05-21T09:12:20Z)
• 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)
• Zero-shot Causal Graph Extrapolation from Text via LLMs [50.596179963913045]
  We evaluate the ability of large language models (LLMs) to infer causal relations from natural language. LLMs show competitive performance in a benchmark of pairwise relations without needing (explicit) training samples. We extend our approach to extrapolating causal graphs through iterated pairwise queries.
  arXiv  Detail & Related papers  (2023-12-22T13:14:38Z)
• Why Can Large Language Models Generate Correct Chain-of-Thoughts? [10.888196404348093]
  We introduce a two-level hierarchical graphical model tailored for natural language generation. We establish a compelling geometrical convergence rate that gauges the likelihood of an LLM-generated chain of thoughts.
  arXiv  Detail & Related papers  (2023-10-20T15:09:46Z)
• Simple Linguistic Inferences of Large Language Models (LLMs): Blind Spots and Blinds [59.71218039095155]
  We evaluate language understanding capacities on simple inference tasks that most humans find trivial. We target (i) grammatically-specified entailments, (ii) premises with evidential adverbs of uncertainty, and (iii) monotonicity entailments. The models exhibit moderate to low performance on these evaluation sets.
  arXiv  Detail & Related papers  (2023-05-24T06:41:09Z)
• Evaluating statistical language models as pragmatic reasoners [39.72348730045737]
  We evaluate the capacity of large language models to infer meanings of pragmatic utterances. We find that LLMs can derive context-grounded, human-like distributions over the interpretations of several complex pragmatic utterances. Results inform the inferential capacity of statistical language models, and their use in pragmatic and semantic parsing applications.
  arXiv  Detail & Related papers  (2023-05-01T18:22:10Z)
• Multimodal Chain-of-Thought Reasoning in Language Models [94.70184390935661]
  We propose Multimodal-CoT that incorporates language (text) and vision (images) modalities into a two-stage framework. Experimental results on ScienceQA and A-OKVQA benchmark datasets show the effectiveness of our proposed approach.
  arXiv  Detail & Related papers  (2023-02-02T07:51:19Z)
• 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)
• Synergies between Disentanglement and Sparsity: Generalization and Identifiability in Multi-Task Learning [79.83792914684985]
  We prove a new identifiability result that provides conditions under which maximally sparse base-predictors yield disentangled representations. Motivated by this theoretical result, we propose a practical approach to learn disentangled representations based on a sparsity-promoting bi-level optimization problem.
  arXiv  Detail & Related papers  (2022-11-26T21:02:09Z)
• Emergent Linguistic Structures in Neural Networks are Fragile [20.692540987792732]
  Large Language Models (LLMs) have been reported to have strong performance on natural language processing tasks. We propose a framework to assess the consistency and robustness of linguistic representations.
  arXiv  Detail & Related papers  (2022-10-31T15:43:57Z)
• Better Language Model with Hypernym Class Prediction [101.8517004687825]
  Class-based language models (LMs) have been long devised to address context sparsity in $n$-gram LMs. In this study, we revisit this approach in the context of neural LMs.
  arXiv  Detail & Related papers  (2022-03-21T01:16:44Z)
• Masked Language Modeling and the Distributional Hypothesis: Order Word Matters Pre-training for Little [74.49773960145681]
  A possible explanation for the impressive performance of masked language model (MLM)-training is that such models have learned to represent the syntactic structures prevalent in NLP pipelines. In this paper, we propose a different explanation: pre-trains succeed on downstream tasks almost entirely due to their ability to model higher-order word co-occurrence statistics. Our results show that purely distributional information largely explains the success of pre-training, and underscore the importance of curating challenging evaluation datasets that require deeper linguistic knowledge.
  arXiv  Detail & Related papers  (2021-04-14T06:30:36Z)

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.