# Extracting Algorithms in Pre-trained LLMs: A Case on Hidden Markov Models

arXiv: https://arxiv.org/abs/2607.22646 · HTML: https://mlsanity.com/paper/2607.22646/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 42 references that are in the map.
- First posted on arXiv 24 Jun 2026.

## Builds on (most cited first, 9 of 9)

- [Towards Best Practices of Activation Patching in Language Models: Metrics and Methods](https://mlsanity.com/paper/2309.16042/) (2023)
- [Interpreting the Repeated Token Phenomenon in Large Language Models](https://mlsanity.com/paper/2503.08908/) (2025)
- [Learning In-context n-grams with Transformers: Sub-n-grams Are Near-stationary Points](https://mlsanity.com/paper/2508.12837/) (2025)
- [On Limitation of Transformer for Learning HMMs](https://mlsanity.com/paper/2406.04089/) (2024)
- [From Kepler to Newton: Inductive Biases Guide Learned World Models in Transformers](https://mlsanity.com/paper/2602.06923/) (2026)
- [Finite Sample Identification of Partially Observed Bilinear Dynamical Systems](https://mlsanity.com/paper/2501.07652/) (2025)
- [What One Cannot, Two Can: Two-Layer Transformers Provably Represent Induction Heads on Any-Order Markov Chains](https://mlsanity.com/paper/2508.07208/) (2025)
- [Bridging the Usability Gap: Theoretical and Methodological Advances for Spectral Learning of Hidden Markov Models](https://mlsanity.com/paper/2302.07437/) (2023)
- [Transformers as Multi-task Learners: Decoupling Features in Hidden Markov Models](https://mlsanity.com/paper/2506.01919/) (2025)

## Abstract (arXiv)

Large language models (LLMs) display a striking ability to predict next observations from Hidden Markov Models (HMMs) via in-context learning (ICL), but the algorithm underlying this capability remains undetermined: prior work has proposed several candidates without consensus, and none has been grounded in the model's internal activations. We close this gap with a three-stage pipeline. First, we empirically compare LLM behavior against a suite of candidate algorithms and narrow the space to three classes -- though no single class explains LLM behavior across all HMM settings and sequence lengths. Second, we derive theoretical connections between the three classes and show how each can be implemented in-context by a Transformer, validating the construction in a small trained Transformer. Third, returning to pre-trained LLMs, we introduce the Principal Activations Probe (PAP), a layer-wise probing and intervention method that isolates algorithmic signals in model activations. PAP reveals low-dimensional linear representations that causally drive model predictions and track empirical ICL performance. PAP further reveals how these representations shift with properties of the underlying HMM regime; distinct computational stages are localized to different layers. Together, our results connect the in-context behavior of pre-trained LLMs to the underlying internal mechanisms and advance our understanding of how LLMs perform ICL on HMMs.