What Algorithms Do Pre-trained LLMs Use for HMM Prediction?

Large language models (LLMs) exhibit a striking ability to predict observations generated by Hidden Markov Models (HMMs) through in-context learning (ICL), yet the algorithms underlying this capability remain unclear. We investigate this question through a three-stage pipeline combining behavioral comparisons, constructive Transformer theory, and causal analysis of internal representations. First, we compare LLM behavior with a suite of candidate algorithms, including classical inference methods and algorithms motivated by empirical observations. Second, we establish theoretical connections among these algorithmic classes, construct in-context Transformer implementations, and validate a finite-window mechanism in a small trained Transformer. Third, we probe pre-trained LLMs for internal representations corresponding to the candidate algorithms. We identify low-dimensional linear representations that causally influence model predictions and whose strength tracks empirical ICL performance. These representations vary systematically across HMM regimes, with finite-window, gradient-descent-like computations predominating in most regimes. Together, our results connect the in-context behavior of LLMs to their internal algorithmic representations, providing a foundation for understanding how LLMs predict sequences governed by latent dynamics.