Scaling Markov Models via Low-Rank Stochastic Factorization

This direction is merged into another direction: low-rank transition factorization. Its last version stays readable and citable here.

Version 1 of 112 papers20 conceptsfrozen 2026-10-04

In many areas of machine learning—from reinforcement learning to natural language processing—we model the world using state-transition systems like Markov Decision Processes (MDPs) or Hidden Markov Models (HMMs). These models rely on a transition matrix $P$, where each entry $P_{ij}$ represents the probability of moving from state $i$ to state $j$.

The fundamental problem is scaling. If a system has $N$ states, the transition matrix has $N^2$ entries. As $N$ grows, storing the matrix becomes impossible, and performing operations like matrix-vector multiplication (required for inference or policy evaluation) becomes computationally prohibitive.

Recent research has converged on a powerful solution: Stochastic Factorization. By decomposing a massive transition matrix into a product of much smaller matrices, we can bypass the quadratic wall and model complex dynamics in high-dimensional spaces.

The Stochastic Factorization Trick

The core idea, pioneered by Andre Barreto and colleagues in Practical Kernel-Based Reinforcement Learning, is to approximate the $N \times N$ transition matrix $P$ as the product of two smaller stochastic matrices:

$$P \approx D \times K$$

Where $D$ is an $N \times r$ matrix and $K$ is an $r \times N$ matrix, with $r \ll N$.

In this setup, $r$ represents a small number of "representative" or "latent" states. Instead of modeling every possible transition between $N$ states, the system models how each state relates to these $r$ latent components. This reduces the number of parameters from $O(N^2)$ to $O(Nr)$, turning a quadratic relationship into a linear one.

Intuition: Transitions via Meta-States

To understand why this works, think of the factorization as a two-step process. In the first step ($D$), the system maps the current state to a distribution over "meta-states." In the second step ($K$), it determines the probability of landing in the next actual state given that meta-state.

Mahsa Ghasemi and ufuk topcu extend this in Identifying Sparse Low-Dimensional Structures in Markov Chains by using a three-way decomposition: $P \approx E \hat{P} D$. Here, $E$ encodes states into a low-dimensional kernel space, $\hat{P}$ performs the transition within that small space, and $D$ decodes the result back to the original state space.

This structure ensures that the "bottleneck" of the computation happens in the $r \times r$ space. Calculating multi-step transitions—which normally requires repeated $N \times N$ matrix multiplications—now scales with $r^2$. If $r$ is small, tasks that previously took months of computation can be finished in minutes.

Preserving Dynamics and Topology

A critical requirement for these factorizations is that they must be stochastic: the rows of the factor matrices must be non-negative and sum to one. This isn't just for mathematical neatness; it ensures the compressed model remains a valid probability system.

Andre Barreto demonstrated that this specific "stochastic factorization trick" mathematically preserves the underlying topology of the original system, including its recurrent classes and periodicities. This means the compressed model doesn't just approximate the numbers; it retains the fundamental dynamical behavior of the original high-dimensional environment.

Speeding Up Inference and Learning

The practical benefits of this approach are most visible in structured probabilistic models. In Low-Rank Constraints for Fast Inference in Structured Models, Justin Chiu and Alexander M Rush apply low-rank constraints to HMMs and PCFGs.

By reframing the marginalization step (summing over latent states) as a sequence of fast matrix-vector products through the low-rank factors, they enabled models to scale to 16,000 latent states. Without factorization, the $O(N^2)$ transition cost would make such a model unusable; with it, the cost becomes $O(Nr)$, allowing for much richer latent representations in natural language tasks.

Similarly, for agents learning in real-time, Incremental Stochastic Factorization for Online Reinforcement Learning provides a way to update these compressed factors as new data arrives. This allows agents to build efficient, low-memory models of their environment from streaming data, facilitating faster policy computation without needing to store the full transition history.

Summary of the Shift

The shift toward stochastic factorization represents a move away from "flat" state representations toward "bottlenecked" representations. By forcing transitions through a low-rank latent space, we gain:

  1. Computational Efficiency: Quadratic costs become linear.
  2. Generalization: The model is forced to learn the "essential" dynamics that govern many states at once.
  3. Scalability: We can apply rigorous Markovian analysis to systems with state spaces that were previously considered "too large to model."

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_scaling_markov_models_via_low_rank_stoch_525388dc,
  title = {Scaling Markov Models via Low-Rank Stochastic Factorization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scaling-markov-models-via-low-rank-stochastic-factorization/rdr_525388dc24f84c2a855af4ad6c3575fe},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_scaling_markov_models_via_low_rank_stoch_525388dc_v1,
  title = {Scaling Markov Models via Low-Rank Stochastic Factorization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scaling-markov-models-via-low-rank-stochastic-factorization/rdr_525388dc24f84c2a855af4ad6c3575fe/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}