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

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 38 of its 52 references that are in the map.
- First posted on arXiv 5 May 2026.

## Builds on (most cited first, 30 of 38)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [BART: Denoising Sequence-to-Sequence Pre-training for Natural Language Generation, Translation, and Comprehension](https://mlsanity.com/paper/1910.13461/) (2019)
- [Overcoming catastrophic forgetting in neural networks](https://mlsanity.com/paper/1612.00796/) (2016)
- [Prefix-Tuning: Optimizing Continuous Prompts for Generation](https://mlsanity.com/paper/2101.00190/) (2021)
- [The Power of Scale for Parameter-Efficient Prompt Tuning](https://mlsanity.com/paper/2104.08691/) (2021)
- [Locating and Editing Factual Associations in GPT](https://mlsanity.com/paper/2202.05262/) (2022)
- [DeBERTa: Decoding-enhanced BERT with Disentangled Attention](https://mlsanity.com/paper/2006.03654/) (2020)
- [Gradient Episodic Memory for Continual Learning](https://mlsanity.com/paper/1706.08840/) (2017)
- [Don't Stop Pretraining: Adapt Language Models to Domains and Tasks](https://mlsanity.com/paper/2004.10964/) (2020)
- [BitFit: Simple Parameter-efficient Fine-tuning for Transformer-based Masked Language-models](https://mlsanity.com/paper/2106.10199/) (2021)
- [Efficient Lifelong Learning with A-GEM](https://mlsanity.com/paper/1812.00420/) (2018)
- [Beyond Accuracy: Behavioral Testing of NLP models with CheckList](https://mlsanity.com/paper/2005.04118/) (2020)
- [AdapterFusion: Non-Destructive Task Composition for Transfer Learning](https://mlsanity.com/paper/2005.00247/) (2020)
- [An Empirical Study of Catastrophic Forgetting in Large Language Models During Continual Fine-tuning](https://mlsanity.com/paper/2308.08747/) (2023)
- [On the Cross-lingual Transferability of Monolingual Representations](https://mlsanity.com/paper/1910.11856/) (2019)
- [MAD-X: An Adapter-Based Framework for Multi-Task Cross-Lingual Transfer](https://mlsanity.com/paper/2005.00052/) (2020)
- [Scaling Data-Constrained Language Models](https://mlsanity.com/paper/2305.16264/) (2023)
- [Continual Learning of Large Language Models: A Comprehensive Survey](https://mlsanity.com/paper/2404.16789/) (2024)
- [The Carbon Footprint of Machine Learning Training Will Plateau, Then Shrink](https://mlsanity.com/paper/2204.05149/) (2022)
- [Lifting the Curse of Multilinguality by Pre-training Modular Transformers](https://mlsanity.com/paper/2205.06266/) (2022)
- [Investigating the Catastrophic Forgetting in Multimodal Large Language Models](https://mlsanity.com/paper/2309.10313/) (2023)
- [Mitigating Catastrophic Forgetting in Large Language Models with Self-Synthesized Rehearsal](https://mlsanity.com/paper/2403.01244/) (2024)
- [Model Editing at Scale leads to Gradual and Catastrophic Forgetting](https://mlsanity.com/paper/2401.07453/) (2024)
- [BREAD: Branched Rollouts from Expert Anchors Bridge SFT & RL for Reasoning](https://mlsanity.com/paper/2506.17211/) (2025)
- [Training Chain-of-Thought via Latent-Variable Inference](https://mlsanity.com/paper/2312.02179/) (2023)
- [Improving Language Plasticity via Pretraining with Active Forgetting](https://mlsanity.com/paper/2307.01163/) (2023)
- [Large Language Models as Markov Chains](https://mlsanity.com/paper/2410.02724/) (2024)
- [From Self-Attention to Markov Models: Unveiling the Dynamics of Generative Transformers](https://mlsanity.com/paper/2402.13512/) (2024)
- [Phi-3 Safety Post-Training: Aligning Language Models with a "Break-Fix" Cycle](https://mlsanity.com/paper/2407.13833/) (2024)
- [Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillation](https://mlsanity.com/paper/2502.01694/) (2025)

## Abstract (arXiv)

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.