Additive Multi-Step Markov Chains and the Curse of Dimensionality in Large Language Models

• URL: http://arxiv.org/abs/2603.04412v1
• Date: Tue, 03 Feb 2026 16:38:26 GMT
• Title: Additive Multi-Step Markov Chains and the Curse of Dimensionality in Large Language Models
• Abstract summary: We explore a theoretically feasible approximation of dynamics using N-order additive Markov chains.<n>The main result of the work is the establishment of a correspondence between an additive multi-step chain and a chain with a step-wise memory function.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large-scale language models (LLMs) operate in extremely high-dimensional state spaces, where both token embeddings and their hidden representations create complex dependencies that are not easily reduced to classical Markov structures. In this paper, we explore a theoretically feasible approximation of LLM dynamics using N-order additive Markov chains. Such models allow the conditional probability of the next token to be decomposed into a superposition of contributions from multiple historical depths, reducing the combinatorial explosion typically associated with high-order Markov processes. The main result of the work is the establishment of a correspondence between an additive multi-step chain and a chain with a step-wise memory function. This equivalence allowed the introduction of the concept of information temperature not only for stepwise but also for additive N-order Markov chains.

Related papers

• Continuous Autoregressive Language Models [56.49239051750678]
  We introduce Continuous Autoregressive Language Models (CALM)<n>CALM uses a high-fidelity autoencoder to compress a chunk of K tokens into a single continuous vector.<n>We develop a comprehensive likelihood-free framework that enables robust training, evaluation, and controllable sampling.
  arXiv  Detail & Related papers  (2025-10-31T17:58:11Z)
• Higher-order Linear Attention [59.92962330635185]
  quadratic cost of scaled dot-product attention is a central obstacle to scaling autoregressive language models to long contexts.<n>We introduce Higher-order Linear Attention (HLA), a causal, streaming mechanism that realizes higher interactions via compact prefix sufficient statistics.
  arXiv  Detail & Related papers  (2025-10-31T07:54:37Z)
• Sequential-Parallel Duality in Prefix Scannable Models [68.39855814099997]
  Recent developments have given rise to various models, such as Gated Linear Attention (GLA) and Mamba.<n>This raises a natural question: can we characterize the full class of neural sequence models that support near-constant-time parallel evaluation and linear-time, constant-space sequential inference?
  arXiv  Detail & Related papers  (2025-06-12T17:32:02Z)
• Low-Rank Tensors for Multi-Dimensional Markov Models [33.35376484951434]
  We present low-rank tensors for representing transition probabilities on multi-dimensional state spaces. Our proposed model yields a parsimonious representation with fewer parameters than matrix-based approaches.
  arXiv  Detail & Related papers  (2024-11-04T14:06:49Z)
• Sparse Modular Activation for Efficient Sequence Modeling [94.11125833685583]
  Recent models combining Linear State Space Models with self-attention mechanisms have demonstrated impressive results across a range of sequence modeling tasks. Current approaches apply attention modules statically and uniformly to all elements in the input sequences, leading to sub-optimal quality-efficiency trade-offs. We introduce Sparse Modular Activation (SMA), a general mechanism enabling neural networks to sparsely activate sub-modules for sequence elements in a differentiable manner.
  arXiv  Detail & Related papers  (2023-06-19T23:10:02Z)
• Disentanglement via Latent Quantization [60.37109712033694]
  In this work, we construct an inductive bias towards encoding to and decoding from an organized latent space. We demonstrate the broad applicability of this approach by adding it to both basic data-re (vanilla autoencoder) and latent-reconstructing (InfoGAN) generative models.
  arXiv  Detail & Related papers  (2023-05-28T06:30:29Z)
• Deep Stochastic Processes via Functional Markov Transition Operators [59.55961312230447]
  We introduce a new class of Processes (SPs) constructed by stacking sequences of neural parameterised Markov transition operators in function space. We prove that these Markov transition operators can preserve the exchangeability and consistency of SPs.
  arXiv  Detail & Related papers  (2023-05-24T21:15:23Z)
• Enabling Quantum Speedup of Markov Chains using a Multi-level Approach [0.0]
  Quantum speedup for mixing a Markov chain can be achieved based on the construction of slowly-varying $r$ Markov chains. We show that the density function of a low-resolution Markov chain can be used to warm start the Markov chain with high resolution.
  arXiv  Detail & Related papers  (2022-10-25T15:17:52Z)
• Generalization Error Bounds on Deep Learning with Markov Datasets [16.3460693863947]
  We derive upper bounds on generalization errors for deep neural networks with Markov datasets. New symmetrization inequalities in high-dimensional probability for Markov chains is a key element in our extension.
  arXiv  Detail & Related papers  (2021-12-23T11:14:43Z)
• An Information-Theoretic Approach for Automatically Determining the Number of States when Aggregating Markov Chains [12.716429755564821]
  We show that an augmented value-of-information-based approach to aggregating Markov chains facilitates the determination of the number of state groups. The optimal state-group count coincides with the case where the complexity of the reduced-order chain is balanced against the mutual dependence between the original- and reduced-order chain dynamics.
  arXiv  Detail & Related papers  (2021-07-05T05:36:04Z)

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.