Memory as a Markov Matrix: Sample Efficient Knowledge Expansion via Token-to-Dictionary Mapping

• URL: http://arxiv.org/abs/2605.04308v1
• Date: Tue, 05 May 2026 21:14:25 GMT
• Title: Memory as a Markov Matrix: Sample Efficient Knowledge Expansion via Token-to-Dictionary Mapping
• Abstract summary: Continual incorporation of new knowledge is essential for the long-term evolution of large language models.<n>Existing approaches typically rely on parameter-update algorithms to mitigate catastrophic forgetting.<n>We propose a principled framework that models autoregressive language generation as a Markov process over tokens.
• Score: 9.065709734849873
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Continual incorporation of new knowledge is essential for the long-term evolution of large language models (LLMs). Existing approaches typically rely on parameter-update algorithms to mitigate catastrophic forgetting, yet they suffer from fundamental limitations: 1) forgetting is unavoidable as the amount of newly injected knowledge grows; and 2) model updates are often irreversible. As modern LLMs become increasingly expressive, it is natural to question whether large-scale weight updates are necessary for acquiring a small amount of new knowledge. In this work, we propose a principled framework that models autoregressive language generation as a Markov process over tokens, where model memory is represented by a Markov transition matrix. Under this formulation, incorporating new knowledge/tokens corresponds to extending the state space, and preserving existing transitions guarantees retention of previously learned knowledge. We then prove a sample complexity bound for incorporating new tokens via a token-to-dictionary mapping strategy. In particular, for learning the transition behavior of each new token, the required number of samples scales linearly with the number of existing tokens it is mapped to. To realize this mapping, we propose an embedding-tuning algorithm that requires minimal parameter updates and induces zero forgetting. Experimental results further demonstrate the effectiveness of our method and validate our theoretical findings.

Related papers

• Improving Sparse Memory Finetuning [6.491055956716639]
  Large Language Models (LLMs) are typically static after training, yet real-world applications require continual adaptation to new knowledge without degrading existing capabilities.<n>Standard approaches to updating models, like full finetuning or parameter-efficient methods, face a fundamental trade-off: catastrophic forgetting.<n>Sparse Memory Finetuning (SMF) offers a promising alternative by localizing updates to a small subset of parameters in explicit memory layers.
  arXiv  Detail & Related papers  (2026-04-06T23:16:10Z)
• 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)
• Comparing Knowledge Injection Methods for LLMs in a Low-Resource Regime [13.230760040927496]
  We investigate the task of injecting small, unstructured information into large language models.<n>We show that simply continuing pre-training on limited data yields modest improvements.<n>We shed light on the forgetting phenomenon in small-data regimes, illustrating the delicate balance between learning new content and retaining existing capabilities.
  arXiv  Detail & Related papers  (2025-08-08T09:48:32Z)
• Training-Free Tokenizer Transplantation via Orthogonal Matching Pursuit [45.18582668677648]
  We present a training-free method to transplant tokenizers in large language models.<n>We approximate each out-of-vocabulary token as a sparse linear combination of shared tokens.<n>We show that OMP achieves best zero-shot preservation of the base model's performance.
  arXiv  Detail & Related papers  (2025-06-07T00:51:27Z)
• Not Every Token Needs Forgetting: Selective Unlearning to Limit Change in Utility in Large Language Model Unlearning [95.53571199301963]
  Conventional unlearning approaches indiscriminately update model parameters to forget all tokens in a target document.<n>We propose Selective Unlearning (SU), which identifies a critical subset of tokens within the forgetting set that is relevant to the unwanted information.<n>Experiments on two benchmarks and six baseline unlearning algorithms demonstrate that SU not only achieves effective unlearning on the targeted forget data, but also significantly preserves the model's utility in the retaining set.
  arXiv  Detail & Related papers  (2025-06-01T07:36:45Z)
• Demystifying Singular Defects in Large Language Models [61.98878352956125]
  In large language models (LLMs), the underlying causes of high-norm tokens remain largely unexplored.<n>We provide both theoretical insights and empirical validation across a range of recent models.<n>We showcase two practical applications of these findings: the improvement of quantization schemes and the design of LLM signatures.
  arXiv  Detail & Related papers  (2025-02-10T20:09:16Z)
• Token Assorted: Mixing Latent and Text Tokens for Improved Language Model Reasoning [53.57895922042783]
  Large Language Models (LLMs) excel at reasoning and planning when trained on chainof-thought (CoT) data.<n>We propose a hybrid representation of the reasoning process, where we partially abstract away the initial reasoning steps using latent discrete tokens.
  arXiv  Detail & Related papers  (2025-02-05T15:33:00Z)
• Turning Trash into Treasure: Accelerating Inference of Large Language Models with Token Recycling [24.04649159686283]
  Speculative decoding is an approach to accelerate inference through a guess-and-verify paradigm.<n> Token Recycling stores candidate tokens in an adjacency matrix and employs a breadth-first-search algorithm.<n>It significantly outperforms existing train-free methods by 30% and even a widely recognized training method by 25%.
  arXiv  Detail & Related papers  (2024-08-16T12:20:56Z)
• Parallel Decoding via Hidden Transfer for Lossless Large Language Model Acceleration [54.897493351694195]
  We propose a novel parallel decoding approach, namely textithidden transfer, which decodes multiple successive tokens simultaneously in a single forward pass. In terms of acceleration metrics, we outperform all the single-model acceleration techniques, including Medusa and Self-Speculative decoding.
  arXiv  Detail & Related papers  (2024-04-18T09:17:06Z)
• Class incremental learning with probability dampening and cascaded gated classifier [4.285597067389559]
  We propose a novel incremental regularisation approach called Margin Dampening and Cascaded Scaling. The first combines a soft constraint and a knowledge distillation approach to preserve past knowledge while allowing forgetting new patterns. We empirically show that our approach performs well on multiple benchmarks well-established baselines.
  arXiv  Detail & Related papers  (2024-02-02T09:33:07Z)
• LabelPrompt: Effective Prompt-based Learning for Relation Classification [31.291466190218912]
  This paper presents a novel prompt-based learning method, namely LabelPrompt, for the relation classification task. Motivated by the intuition to GIVE MODEL CHOICES!'', we first define additional tokens to represent relation labels, which regard these tokens as the verbaliser with semantic initialisation. Then, to mitigate inconsistency between predicted relations and given entities, we implement an entity-aware module with contrastive learning.
  arXiv  Detail & Related papers  (2023-02-16T04:06:25Z)
• New Insights on Reducing Abrupt Representation Change in Online Continual Learning [69.05515249097208]
  We focus on the change in representations of observed data that arises when previously unobserved classes appear in the incoming data stream. We show that applying Experience Replay causes the newly added classes' representations to overlap significantly with the previous classes. We propose a new method which mitigates this issue by shielding the learned representations from drastic adaptation to accommodate new classes.
  arXiv  Detail & Related papers  (2022-03-08T01:37:00Z)
• Representation Memorization for Fast Learning New Knowledge without Forgetting [36.55736909586313]
  The ability to quickly learn new knowledge is a big step towards human-level intelligence. We consider scenarios that require learning new classes or data distributions quickly and incrementally over time. We propose "Memory-based Hebbian Adaptation" to tackle the two major challenges.
  arXiv  Detail & Related papers  (2021-08-28T07:54: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.