Training-Free Tokenizer Transplantation via Orthogonal Matching Pursuit
Authors: name: Charles Goddard, name: Fernando Fernandes Neto

We present a training-free method to transplant tokenizers in pretrained
large language models (LLMs) by reconstructing unseen token embeddings via
Orthogonal Matching Pursuit (OMP). Specifically, we approximate each
out-of-vocabulary token as a sparse linear combination of shared tokens, in two
phases: first, compute each new token's representation in the donor embedding
space with a small dictionary of shared anchor tokens, then transfer these same
sparse coefficients back into the base model's embedding space.
  On two challenging cross-tokenizer tasks--LlamatoMistral NeMo (12B) and
QwentoLlama (1B)--we show that OMP achieves best zero-shot preservation of
the base model's performance across multiple benchmarks, while other zero-shot
approaches degrade significantly. Compared to baselines (zero-init, mean-init,
and existing approaches like WECHSEL, FOCUS, ZETT), OMP consistently achieves
the best overall performance, effectively bridging large tokenizer
discrepancies without gradient updates. Our analysis further identifies
mismatched numerical tokenization schemes as a critical challenge for
preserving mathematical reasoning capabilities. This technique enables direct
reuse of pretrained model weights with new tokenizers, facilitating
cross-tokenizer knowledge distillation, speculative decoding, ensembling,
merging, and domain-specific vocabulary adaptations. We integrate our method
into the open-source mergekit-tokensurgeon tool for post hoc vocabulary
realignment.