Lossless Vocabulary Reduction for Auto-Regressive Language Models

AI summary

Overview

Research area: Natural Language Processing, specifically tokenization, auto-regressive language models, and model interoperability. Technical level: Advanced, because the paper builds a probability-theoretic framework with formal definitions, lemmas, and theorems. Scope: The paper introduces lossless vocabulary reduction, a method to convert a token-level auto-regressive language model into an equivalent model over an arbitrary sub-vocabulary, and applies it to ensemble across different tokenizations.

What This Paper Is About

Auto-regressive language models generate text token by token, and each model has its own vocabulary built from its training data. Because vocabularies differ, models with different tokenizers cannot easily cooperate at the level of next-token distributions, which limits ensemble, knowledge distillation, speculative decoding, and inference-time alignment. The paper's goal is to reduce a model's next-token distribution to an arbitrary sub-vocabulary without changing its behavior as a text generator, then use a maximal common vocabulary so models with different tokenizations can cooperate efficiently.

Key Contributions

1. It establishes the first theoretical framework of lossless vocabulary reduction, introducing nested tokenization and proving that reduction to an arbitrary sub-vocabulary preserves the induced text distribution.
2. It derives a recursive formula and exact algorithm for computing the reduced next-token distribution from the original next-token distribution, using a generalized notion of relative covering.
3. It provides an efficient approximated algorithm called Top-K Approximation (K-LVR) intended to compute lossless vocabulary reduction with negligibly small overhead.
4. It applies the framework to model ensemble with different tokenization, proposing reduction to the maximal common vocabulary among models and showing empirically that this ensemble is comparable to byte-level ensemble while being more efficient.

Main Findings

• Lossless property: The vocabulary-reduced model over a sub-vocabulary has the same text distribution as the original model and the true text distribution: p_{V->V_sub->A}(a_{1:N}) = p_{V->A}(a_{1:N}) = p_text(a_{1:N}).
• Generalizes prior byte-level reduction: When the sub-vocabulary is the set of bytes A, vocabulary reduction becomes the byte-level reduction studied by Phan et al. (2025) and Vieira et al. (2025).
• Recursive computation: The relative covering C_{V,V_sub}(y_{1:k}) and its subsets C^eq and C^(l) allow decomposition of probabilities into two cases, yielding the formula in Theorem 3.4 for computing p_{V->V_sub}(y_{1:k}*).
• Exact and approximate algorithms: Algorithm 1 computes the exact reduced next-token distribution using caches for probabilities and relative minimal covers. Algorithm 2 gives the Top-K Approximation, called K-LVR.
• Illustrative example: With A={0,1}, V={⟨0⟩,⟨1⟩,⟨00⟩,⟨001⟩}, and V_sub={⟨0⟩,⟨1⟩,⟨00⟩}, the paper shows both p_V and p_{V->V_sub} assign probability 0.5 to the output text starting from "000", matching the lossless property.
• Empirical validation stated in the paper: Experimental results with several language models show that the derived algorithm is almost lossless as the theory suggests. Ensemble over the maximal common vocabulary achieves comparable accuracy to the byte-level ensemble while being more efficient.
• Reporting limits in the provided content: Specific language model names, dataset sizes, benchmark names, and exact accuracy metrics are not reported in the provided paper content.

Methodology in Plain English

The authors treat text as sequences of bytes and formalize tokenization as an encoder-decoder pair. They define a nested tokenization that takes tokens from the original vocabulary and re-tokenizes them into tokens from a chosen sub-vocabulary. Vocabulary reduction is then defined as the distribution over sub-vocabulary token sequences that results from re-tokenizing sequences sampled from the original model.

To prove the reduction is lossless, they show that reducing to a sub-vocabulary and then reducing again to bytes gives exactly the same text distribution as reducing the original model directly to bytes. For practical computation, they introduce relative covering, which collects original token sequences whose re-tokenization is consistent with a given sequence of sub-vocabulary tokens. They prove lemmas that decompose these coverings into two cases, leading to a recursive formula for marginal probabilities and next-token probabilities. Algorithm 1 implements this exact computation, while Algorithm 2, the Top-K Approximation (K-LVR), approximates it efficiently. The application to ensemble is straightforward: reduce each language model to their maximal common vocabulary, then ensemble at that shared token level.

Why This Matters

Impact on research: The paper moves beyond byte-level reduction to arbitrary sub-vocabularies, giving a general theoretical foundation for making auto-regressive language models with different tokenizations cooperate without changing their text-generation behavior. This could unify approaches to ensemble, distillation, speculative decoding, and inference-time alignment across incompatible tokenizers.

Real-world applications:

• Ensembling language models trained with different tokenizers without converting everything to bytes, which avoids the increased inference cost of byte-by-byte prediction.
• Knowledge distillation between teacher and student models that use different vocabularies.
• Speculative decoding where draft and target models have different tokenizations.
• Inference-time alignment or decoding-time interventions that require multiple models to share a next-token distribution.

Industry relevance: The framework supports interoperability among independently trained language models, more efficient multi-model serving, and easier combination of proprietary or open models with different tokenizers. The paper does not report specific industry benchmarks or deployment metrics.

Future Directions

• Extend the theory beyond deterministic tokenization, since the paper explicitly focuses only on deterministic tokenization.
• Conduct broader empirical evaluation with named language models, datasets, and benchmarks, because the provided content does not report these details.
• Develop error bounds or approximation guarantees for the Top-K Approximation (K-LVR) and study the trade-off between K and accuracy.
• Investigate how to choose the sub-vocabulary or maximal common vocabulary to balance efficiency and accuracy in different cooperation settings.
• Apply the framework to the other cooperation scenarios named in the paper: knowledge distillation, speculative decoding, and inference-time alignment.

Target Audience

Researchers in NLP and machine learning who work on tokenization, language model theory, model ensembling, and multi-model systems. Practitioners building systems that combine language models with different tokenizers will also benefit. The paper is best suited to readers with some background in probability, auto-regressive modeling, and tokenization; beginners may need additional preparation.

Authors’ abstract

Tokenization -- the process of decomposing a given text into a sequence of subwords called tokens -- is one of the key components in the development of language models. Particularly, auto-regressive language models generate texts token by token, i.e., by predicting the next-token distribution given the previous ones, and thus tokenization directly affects their efficiency in text generation. Since each language model has their own vocabulary as a set of possible tokens, they struggle to cooperate with each other at the level of next-token distributions such as model ensemble. In this paper, we establish a theoretical framework of lossless vocabulary reduction, which efficiently converts a given auto-regressive language model into the one with an arbitrarily small vocabulary without any loss in accuracy. This framework allows language models with different tokenization to cooperate with each other efficiently by reduction to their maximal common vocabulary. Specifically, we empirically demonstrate its applicability to model ensemble with different tokenization.