Memory as a Markov Matrix: Solving Catastrophic Forgetting with Token-to-Dictionary Mapping

TL;DR

Acquiring new knowledge in LLMs usually comes at the cost of "forgetting" the old. This paper proposes a paradigm shift: treating the LLM as a Markov Transition Matrix. By interpreting new tokens as new states in a Markov chain and mapping them to a dictionary of existing embeddings, the authors achieve zero catastrophic forgetting and provable sample efficiency.

The Problem: Why Does Fine-Tuning Break Models?

When we fine-tune an LLM on new data, we typically update the transformer's weights ($W$). Because these weights are "shared" across all tasks, a gradient update intended to help the model learn a new word (e.g., "DOGE" as a department) inevitably shifts the manifold for existing words.

The authors demonstrate this drastically: fine-tuning a model to learn a new symbol <spec> for multiplication causes the model to completely forget how to perform addition. The model doesn't just get worse; it creates a "disabled edit" where the original logic is overwritten.

The Insight: Language Models as Markov Processes

The core contribution of this work is a shift in perspective. If we view next-token prediction as a Markovian state transition, the model's memory is essentially a transition matrix $P$ where $P_{ij}$ is the probability of moving from token $i$ to token $j$.

• Existing Knowledge: The transitions between existing tokens $VoV$.
• New Knowledge: The transitions from new tokens $UoV$.

To prevent forgetting, we must keep the $VoV$ transitions invariant. The simplest way to do this? Leave the backbone weights alone and only update the entry-point (embeddings) for the new tokens.

Methodology: Token-to-Dictionary Mapping

Instead of full-parameter updates, the authors propose Embedding Tuning (ET).

1. State Space Expansion: Add new tokens $U$ to the vocabulary.
2. Mapping: Represent each new token $u$ as a sparse combination of existing tokens. For example, a new arithmetic operator might be mapped to a combination of "$imes$", "multiplied", and "times".
3. Optimization: Only the embedding vector $e(u)$ is trained. Since the transformer weights are frozen, the $VoV$ paths remain physically untouched.

Theoretical Guarantee

The paper proves a Sample Complexity Bound: If a new token $u$ can be represented as an $s$-sparse combination of existing tokens, the number of samples $N$ required to learn it scales as $O(s\log (T))$, where $T$ is the vocabulary size. Crucially, it does not depend on the number of model parameters, making it highly efficient for massive models.

Figure: The mapping strategy ensures that new tokens are integrated into the existing Markovian structure without isolated subdynamics.

Experimental Results: The End of Forgetting

The authors tested this across arithmetic, synthetic vocabulary, and real-world cross-lingual tasks.

1. Arithmetic Preservation

When learning a new multiplication operator:

• FFT (Full Fine-Tuning): Accuracy on addition dropped from 100% to 0%.
• ET (Embedding Tuning): Accuracy on addition remained 100%.

2. Cross-Lingual Results

When adapting an English model (Qwen2.5-3B) to Arabic, Spanish, and German:

• ET achieved lower loss on the target languages than LoRA or FFT.
• Forgetting on English was 0.00 (or even negative, meaning English improved slightly).

Table: Comparison of loss and forgetting across Spanish, German, and Arabic.

Critical Analysis & Conclusion

The beauty of this approach lies in its simplicity and theoretical rigor. While many researchers have explored embedding tuning empirically, this paper provides the Markovian justification for why it works—and why it is the only way to guarantee zero forgetting in the state-transition sense.

Limitations

1. Context-Free Assumption: The basic theory uses a 1st-order Markov chain. While they discuss higher-order extensions, real-world LLMs have extremely complex dependencies that might push the "sparsity" ($s$) higher than expected.
2. No Backbone Growth: This method assumes the model already has enough "latent concepts" to represent the new token. If you are teaching a model a concept it has never even remotely encountered (e.g., 4D spatial reasoning), a simple mapping to existing tokens might fail.

Final Takeaway

This work suggests that for many "knowledge update" tasks, we are over-engineering our training. We don't need to rebuild the brain to learn a new name; we just need to learn how that name relates to what we already know. Embedding Tuning is the mathematical embodiment of that intuition.