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

• URL: http://arxiv.org/abs/2607.22646v1
• Date: Wed, 24 Jun 2026 17:42:19 GMT
• Title: Extracting Algorithms in Pre-trained LLMs: A Case on Hidden Markov Models
• Abstract summary: Large language models (LLMs) display a striking ability to predict next observations from Hidden Markov Models (HMMs) via in-context learning (ICL)<n>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.<n>Second, we derive theoretical connections between the three classes and show how each can be implemented in-context by a Transformer.<n>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 activation
• Score: 12.294879009851476
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Large Language Models Develop Belief State Geometry In-Context [1.6972273159174482]
  Large language models (LLMs) trained on next-token prediction exhibit remarkable in-context learning abilities.<n>We consider such representations in a controlled setting, prompting LLMs with data emitted from hidden Markov models.<n>We find that belief states are linearly decodable from residual stream activations.
  arXiv  Detail & Related papers  (2026-09-15T16:17:59Z)
• Modularized Reinforcement Learning on LLMs: From MDP Creation to Exploration and Learning [65.72189367176186]
  This survey organizes that examination around three stages of algorithm construction.<n>We begin with MDP creation: how the reward function, state space, action space, termination condition, and discount factor are, or could be, defined for LLM training.<n>We then turn to exploration, covering temperature sampling, entropy regularization, intrinsic motivation, tree search, and curriculum learning.
  arXiv  Detail & Related papers  (2026-06-20T08:20:41Z)
• Modular Representation Compression: Adapting LLMs for Efficient and Effective Recommendations [53.53864188270018]
  Large language models (LLMs) have advanced recommendation systems (RSs)<n>We propose MARC to explicitly control the modularity of LLMs.<n>MARC achieved a 2.82% eCPM lift in an online A/B test within a large-scale commercial search advertising scenario.
  arXiv  Detail & Related papers  (2026-04-20T12:08:58Z)
• Fine-Tuning Causal LLMs for Text Classification: Embedding-Based vs. Instruction-Based Approaches [0.0]
  We explore strategies to fine-tune decoder-only Large Language Models (LLMs) for downstream text classification under resource constraints.<n>Two approaches are investigated: (1) attaching a classification head to a pre-trained causal LLM and fine-tuning on the task, and (2) instruction-tuning the LLM in a prompt->response format for classification.
  arXiv  Detail & Related papers  (2025-12-14T13:02:06Z)
• Principled and Tractable RL for Reasoning with Diffusion Language Models [0.0]
  Diffusion large language models (dLLMs) are trained to predict multiple tokens in parallel and generate text via iterative unmasking.<n>Recent works have successfully pretrained dLLMs to parity with autoregressive LLMs at the 8B scale, but dLLMs have yet to benefit from modern post-training techniques.<n>We present Amortized Group Relative Policy Optimization (AGRPO), a principled on-policy RL algorithm designed specifically for dLLMs.
  arXiv  Detail & Related papers  (2025-10-05T03:53:16Z)
• Satori: Reinforcement Learning with Chain-of-Action-Thought Enhances LLM Reasoning via Autoregressive Search [57.28671084993782]
  Large language models (LLMs) have demonstrated remarkable reasoning capabilities across diverse domains.<n>Recent studies have shown that increasing test-time computation enhances LLMs' reasoning capabilities.<n>We propose a two-stage training paradigm: 1) a small-scale format tuning stage to internalize the COAT reasoning format and 2) a large-scale self-improvement stage leveraging reinforcement learning.
  arXiv  Detail & Related papers  (2025-02-04T17:26:58Z)
• Scaling Laws for Predicting Downstream Performance in LLMs [75.28559015477137]
  This work focuses on the pre-training loss as a more computation-efficient metric for performance estimation.<n>We present FLP-M, a fundamental approach for performance prediction that addresses the practical need to integrate datasets from multiple sources during pre-training.
  arXiv  Detail & Related papers  (2024-10-11T04:57:48Z)
• An Effective Approach to Embedding Source Code by Combining Large Language and Sentence Embedding Models [6.976968804436321]
  This paper proposes a novel approach to embedding source code by combining large language and sentence embedding models.<n>To evaluate the performance of our proposed approach, we conducted a series of experiments on three datasets with different programming languages.
  arXiv  Detail & Related papers  (2024-09-23T01:03:15Z)
• On the Relation between Internal Language Model and Sequence Discriminative Training for Neural Transducers [52.88268942796418]
  Internal language model (ILM) subtraction has been widely applied to improve the performance of the RNN-Transducer. We show that sequence discriminative training has a strong correlation with ILM subtraction from both theoretical and empirical points of view.
  arXiv  Detail & Related papers  (2023-09-25T13:35:28Z)
• Response Length Perception and Sequence Scheduling: An LLM-Empowered LLM Inference Pipeline [22.08897444328099]
  Large language models (LLMs) have revolutionized the field of AI, demonstrating unprecedented capacity across various tasks. In this paper, we propose an efficient LLM inference pipeline that harnesses the power of LLMs.
  arXiv  Detail & Related papers  (2023-05-22T15:36:06Z)
• Understanding Emergent In-Context Learning from a Kernel Regression Perspective [55.95455089638838]
  Large language models (LLMs) have initiated a paradigm shift in transfer learning.<n>This paper proposes a kernel-regression perspective of understanding LLMs' ICL bahaviors when faced with in-context examples.<n>We find that during ICL, the attention and hidden features in LLMs match the behaviors of a kernel regression.
  arXiv  Detail & Related papers  (2023-05-22T06:45:02Z)
• LLM-Pruner: On the Structural Pruning of Large Language Models [65.02607075556742]
  Large language models (LLMs) have shown remarkable capabilities in language understanding and generation. We tackle the compression of LLMs within the bound of two constraints: being task-agnostic and minimizing the reliance on the original training dataset. Our method, named LLM-Pruner, adopts structural pruning that selectively removes non-critical coupled structures.
  arXiv  Detail & Related papers  (2023-05-19T12:10:53Z)

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.