Cross-Tokenizer Likelihood Scoring Algorithms for Language Model Distillation
Authors: Buu Phan
Ashish J Khisti
Karen Ullrich
Venue: ICLR 2026 Poster (2026)
Keywords: Tokenization
likelihood scoring
language models
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
TL;DR: TL;DR: Algorithms to compute token sequences under a target BPE vocabulary that differs from the model’s native tokenizer.

Abstract: Computing next-token likelihood ratios between two language models (LMs) is a standard task in training paradigms such as knowledge distillation. Since this requires both models to share the same probability space, it becomes challenging when the teacher and student LMs use different tokenizers, for instance, when edge-device deployment necessitates a smaller vocabulary size to lower memory overhead. This work addresses this vocabulary misalignment problem by uncovering an implicit recursive structure in the commonly deployed Byte-Pair Encoding (BPE) algorithm and utilizing it to create a probabilistic framework for \textit{cross-tokenizer likelihood scoring}. Our method enables sequence likelihood evaluation for vocabularies different from the teacher model native tokenizer, addressing two specific scenarios: when the student vocabulary is a subset of the teacher vocabulary, and the general case where it is arbitrary. In the subset regime, our framework computes exact likelihoods and provides next-token probabilities for sequential sampling with only $\mathcal{O}(1)$ model evaluations per token. When used for distillation, this yields up to a 12% reduction in memory footprint for the Qwen2.5-1.5B model while also improving baseline performance up to 4\% on the evaluated tasks. For the general case, we introduce a rigorous lossless procedure that leverages BPE recursive structure, complemented by a fast approximation that keeps large-vocabulary settings practical. Applied to GSM8K mathematical reasoning distillation, our method improves accuracy by over 2%  the current state of the art. Code: https://github.com/truongbuu/cross-tokenizer-scoring

Published as a conference paper at ICLR 2026
CROSS-TOKENIZER LIKELIHOOD SCORING ALGORITHMS FOR LANGUAGE MODEL DISTILLATION
Buu Phan'
Ashish Khisti'
Karen Ullrich²
'University of Toronto MMeta AI
www.onto..c..a.. truong phan@mail..toorontoooco
akhisti@ece. utoronto.ca otrrstttece..tcrrntoo..ca karenu@meta.com com
ABSTRACT
Computing next-token likelihood ratios between two language models (LMs) is standard task in training paradigms such as knowledge distillation. Since this requires both models to share the same probability space, it becomes challenging when the teacher and student LMs use different tokenizers, for instance, when edge-device deployment necessitates a smaller vocabulary size lower memory overhead. This work addresses this vocabulary misalignment problem by uncovering an implicit recursive structure in the commonly deployed Byte-Pair Encoding (BPE) algorithm and utilizing to create probabilistic framework for cross-tokenizer likelihood scoring. Our method enables sequence likelihood evaluation for vocabularies different from the teacher model native tokenizer, addressing two specific scenarios: when the student vocabulary is a subset of the teacher vocabulary, and the general case where it is arbitrary. the subset regime, framework computes exact likelihoods and provides next- token probabilities for sequential sampling with only (1)) model evaluations per token. When used for distillation, this yields up 12% reduction in memory footprint for the Qwen2.5-1 1,5B model while also improving baseline performance up 4% on the evaluated tasks. For the general case, introduce rigorous lossless procedure that leverages BPE recursive structure, complemented by a fast approximation that keeps large-vocabulary settings practical. Applied to GSM8K mathematical reasoning distillation, our method improves accuracy by over 2% the current state of the art. Code: gittabbommtrogguuuuuccoooooooooe
INTRODUCTION
Many advanced training techniques for language models (LMs) rely computing next-token likelihood ratios between two models. For example, reinforcement learning (Shao et al., 2024) and preference optimization (Zeng et al.] (202)) such ratios bias bias-adjustment terms, ensuring that the learning signal received by the policy network is weighted properly. Similarly, in distillation (Hinton al., 2015), the student model is trained to align with the teacher's next-token distribution to obtain richer learning signals and improved sample efficiency compared to supervised fine-tuning labels. However, computing these ratios is always possible because requires both LMs to share the same probability space, which can fail when the LMs employ different vocabulary-a misalignment issue that has recently drawn attention in LM distillation Shin et al. 2025 Minixhofer et al. 2024| Zhang et al. 2024).
with
Consider the problem of LM distillation. due to the difference in output spaces, it becomes challenging to define what alternative objective could replace the divergence minimization objective between their next-token distributions. Importantly, we note that this misalignment also arises in the input space due to tokenization bias (Phan et 2023 Minixhofer et al. 2025). phenomenon that determines which token cannot appear as a next-token. For example, suppose we use Llama3 as the teacher model, then given the input prompt 111+11=12, tokenized as [111, +, 11, 12] coomma-separatee the teacher model will never output 2 as the next token. This is because 122 is single token in the Llama3 tokenizer, making the sequence [12, 2] impossible in the tokenized text. Consequently, if the student model employs a byte-level tokenizer, this discrepancy creates a misleading training signal, degrading performance.

---

Published as a conference paper at ICLR 2026
Native Tokenizer: Qwen2.5
Target Tokenizer: Gemma2
Conversion Algorithm
Qwen2.5-1.5B
cross
ocab
dist
illation
cross
vocab
distillation
Next-Token Probability
0.21
0.55
0.73
0.96
0.82
0.18
0.47
0.62
0.71
Scoring: given a language model trained on fixed tokenizer, for example Qwen2.5, we aim to compute the probability that this model assigns to sequences encoded with different tokenizer, e.g. Gemma2.
Figure I:
Current approaches to address this issue often introduce additional auxiliary loss functions, such as the Wasserstein distance in the logit space (Boizard et al., 2025), or incorporate extra components like sequence alignment (Minixhofer et al.) (025).. Compared to scenarios where both models use the same tokenizer, these components introduce additional hyperparameters into the pipeline, deviating from the simplicity of Kullback-Leibler (KL) divergence minimization. In this work, we investigate the vocabulary misalignment problem through the lens of stochastic analysis and demonstrate that it is possible re-align the teacher scoring model with the student vocabulary, see Figure 1 recovering the classic next-token divergence minimization/ likelihood ratio problem without introducing additional components. We refer this process as "cross-tokes trosssttokenizer scoring" or "conversion" " and provide a formal formulation in Section Our analysis centers on the widely used Byte Pair Encoding (BPE) tokenization algorithm and demonstrates that if the student vocabulary subset of the one employed by the teacher, there is efficient algorithm to convert the teacher model to score on the token sequences from the student vocabulary. This relates to the vocabulary trimming problem for small LMs (Cognetta et al. 2024 Ushio et al. (203).. which requires reducing the vocabulary size to satisfy resource constraints, i.e. minimizing the language modeling head memory footprin We then extend this result to the general cross-tokenizer scenario where the teacher and student vocabularies differ Our analysis yields a lossless but computationally intensive recursive algorithm compute exact likelihoods in this setting, complemented by a more efficient beam search- based scheme that accurately approximates the ground-truth likelihood scores.
Overall, our contributions are follows:
1. We develop technical insight into the structure of the BPE algorithm and introduce novel concept relative alphabets. Leveraging this concept, we propose an O(1) next-token scoring algorithm for the case where the student vocabulary is subset of the teacher's.
2. We provide an algorithm for conversion in the general case where teacher and student vocabularies differ, deriving a lossless recursive algorithm and a faster beam-search-baar approximation.
3. We conduct extensive experiments to demonstrate the effectiveness of our methods in the cross-tokenizer distillation and vocabulary trimming task.
2 BACKGROUND
Notations. Let A = {ag, a1...., C.A)) denote the initial alphabet, where og = EOS is the end- of-string symbol unless stated otherwise. Following previous works (Phan et al. [025] Vieira al.) 2025a), the EOS symbol marks the termination of character sequence and is treated
standalone token that does not appear as part any other token. We distinguish between an infinite character sequence and finite string s, which has length [s]. If a character sequence has EOS at index I; = EOS, then all subsequent entries must also be EOS, i.e., I; = EOS for all j > i. Thus, effectively, the set of all sequences is countably infinite. In contrast, finite string does not necessarily end with EOS. For a character sequence x, we define its length | as the number of characters up and including the first occurrence of EOS.
vocabulary V is a list tokens such that A C V, and we denote individual tokens as E V. An encoding of string is sequence of tokens encode(s) of length jē), and the corresponding
Recent work by Tao et al. 2024 on scaling laws vocahulary size demonstrates log-log relationship. suggesting that smaller language models benefit from smaller vocahularies. Both vocabularies are derived from the same base alphahet, i.e., UTF-8 bytes.
2

---

Published as a conference paper at ICLR 2026
V. relative alphabet of V, <
V
Vh
Merge Operator
Input: Evv oves Var
Output: 6y---1 over Var+1
@Verus +- 1+1
while évvll:
Alphabet A
a1
if By.r [i],,v,, 15 1] tares:
6 append
else:
Ev append(év (
%1,41
...
9,41
a
Demerge Operator
f
f2
f
f1
Inpuu:: : 6VM+: over Vo4e
Output: 6ya
Var
82
f2
Êvy. < [1] <
while 1 6v
Added Tokens
Following (2)
if 6v = fa++1
By appeeeeed((aaa (elene)
f
fxs-1
else:
@y appeedd(ee
txr
return
Bysr
Figure 2: Progressive construction of BPE vocabulary and pscudocode for the merge and demerge operations. Newly added token at each step is constructed from two tokens within V,-1 and thus any prior vocabulary V; for i j can be considered an alphabet of Vj-
decode(e). Further details on how these mappings are defined are in Section 3 We use e j] to denote the subsequence tokens from index to j. inclusive. Also, ē denotes the encoding obtained by appending the token é to the sequence é. For an encoding C, we use I-based indexing. The slice ali :]] includes elements from the i-th to the j-th position, totaling j
decoding is the string
elements. The notations e|: i) and ēlé :] represent the subarrays from the start to the i-th element and from the i-th element to the end, respectively, both including e(t]. The term é[-1], 6[-1)_ refers the last, second last, etc., token in the encoding.
Language Models. We view a LM Py over a vocabulary as a stochastic process that generates tokens from V in autoregressive manner. For encoding Gy E V", (v-(e)) denotes the (joint) probability that this stochastic process generates a sequence with a prefix ē. Following previous works (Phan al. 2025 Vieira al. 2025b). BPE encoding is valid (canonical) if and only if:
(ncode(decodee()))
otherwise it is invalid (non-canonical), Note that if é is invalid, then we have (v(e) 0.0. For the rest of this work, we assume that the given LMs will always oulput valid encodings, which is compatible with the model's behavior in practice (Vieira et al. 2025b).
SEQUENTIAL STRUCTURE IN BYTE-PAIE ENCODING
In this section, we build the foundational tools required for deriving the conversion algorithm. We begin by formalizing structure of BPE encoding and decoding through the lens of subset vocabularies. We then introduce the key notion of the relative alphabet, which plays central role in the conversion algorithms developed in Section
3.1 SUBSET VOCABULARIES
We first review the structure of BPE vocabulary (Sennrich al. 2015 Gage 1994) and introduce the new concept vocabulary subsets and sequential decoding through demerging. Definition 1. Let A be the alphabet defined in Section 2 A BPE vocabulary Var is ordered list of (LA) + M) tokens consisting of the alphabet AA and M additional tokens constructed sequentially:
VM {ao, 01,..., "[Ai= 41, d,,,..,,AM L,r).
where each merged token t; is defined recursively as
left
right
with sleft gright

---

Published as a conference paper at ICLR 2026
We highlight that tleft t * EOS (i.e., ag) for all i and they must strictly follow the ordering requirement in (2). Also, Definition [ does not concern the method used to obtain the vocabulary, ie., which datasets used to train the tokenizer.
Definition 2 (BPE Vocabulary Subset), For any M' I M, the truncated vocabulary (or BPE vocabulary subset) is
VM {ao, (1,...,......................... :AA]- 11,
which contains the first M' merged tokens VM. We write V.r Var to indicate that VMr is subset of VM in the merge-order sense, and note that Vo=A. Figure visualizes this definition.
Notation Simplification. We briefly note that the notations Vo, Vi.....ar... Vas are reserved for vocabularies defined with construction in Definition ! and to avoid notation overwhelming. We also denote Po. PM for the LM associated with these vocabularies. Otherwise, for any two vocabularies without this subset relation, we will use Va and V/3
BPE Encoding and Decoding. Let Var be BPE vocabulary constructed from an initial alphabet
A. with intermediate vocabularies V; defined for 0 S i S M. Given input string s, the encoding of s with respect to VM is defined as:
V encode(s; VM), or simply Tyy = encode(s; M).
The encoding process begins from the character-level sequence Cg A and applies sequence of merge operations, shown in F
cv2 merge(ev...) V.) A merge,(ev..) for i 1.2...... M,
(3)
where each merge applies the i-th merge rule in the construction of VM-
Sequential Decoding. The default decoding strategy simply maps each token to its surface alphahet form and concatenates the results. Instead, we reinterpret this process as sequence of demerge
operations. Specifically, we define:
8 = decode(ēvs. VM) or simply
= decode ; M).
Starting from Ty we apply the inverse of the i-th merge rule using a demerge function associated with vocabulary V4, see Figure (
d. = demerge(Cv, V.) A (emerge,(Gv,) for = M, .1....,,
(4)
The process terminates at the character-level string ey:
3.2 RELATIVE ALPHABET
Let VaN < Vas, and are given an encoding ēv... = encode(s; M') of string tokenized with VMr. We begin with the following question: how can we obtain the corresponding encoding s under the full vocabulary Var? A direct approach is to decode Ey to recover the original string s, and then re-encode it using Var This two-step procedure can be expressed as:
(1) Decode: s = decode(@y,, M') (2) Encode: εyY, = encode(s; M).
(5)
This requires going through the intermediate representation, i.e. the string s, which redundant. From Equation (3), we compute directly εya, by continuing the merge operations from i = M' + 1 to M. Conversely, to convert an encoding ēyn under Va to one under Vas,. we can directly apply the demerge operations for i M, M-1, 1...... M + 1. Recall that the function encode(,; M) and decode(.;; .M are also defined as a series of merge and demerge steps, we thus can view the subset vocabulary VMP as an intermediate (or relative) alphabet of VM
Definition 3 (Relative Alphabet). If VM 3 VM, then Vas is a relative alphaber with respect to VM. The relative encoding and relative decoding function that maps encoding ev from VMP to E from VM and back are defined as:
GFH encodesr ēy decode ((v
(6)
where:
encode>r=: (ev,r)) merge merge (ē
(7)
decodess dlemergemas M1 o demerge Monnergeaar (0
(8)
4

---

Published as a conference paper at ICLR 2026
Prior Work
Relative Alphabet Framework BPE Tokenizer (Ours)
(hhan 2025
Va
Vi. 7
Vi.a
Directly Intractable
VB
Vi+2.8
V++1.8
Original Vocab
General Case Conversion between two BPE Vocabularies by Recursively Applying Adjacency Case, I. Lemma
Byte Alphabet
Figure 3: Left: Prior work (Phan et al. 2025 supports tractable conversion only from the full BPE vocabulary the byte-level alphabet. Right: Our relative alphabet framework in Definition enables conversion between any pair of BPE vocabularies by first mapping tokens to their byte-level representation, and then recursively applying reverse conversions between adjacent vocabularies (see Section and Lemma where Vi, are the sub-vocabs containing the first i merges of V3.
Following this definition, now introduce the concept of relative cover encodings, which generalizes the notion of cover encodings from (Phan et al. 2025) to the case of relative alphabet.
Definition 4 (Relative Cover Encodings). Let VAs I VM, and let čM be a valid encoding over the vocabulary VMr We say that an encoding εyy, over VM is a relative cover encoding of GV if the following conditions hold:
1. There exists sequence X such that Œy encode(X;; M)(: @v ll.
2. There exists an index
@v such that:
(ev [L:|ēvM/ 1]) Ev [1: 1),
vy [i:] E prefix (decodeas- (ēV [-1]))
i.e. the last token of ŒvE, starts from some location within čy...
We denote by coverar-=>a (Gv ) the set of all such relative cover encodings of ōv..- Example Let Vo (a.b). b). V1 {a, b, a bb and V/2 = (a, b, a bb, ab a). Then we have cover]-=2([a, ab)) {[=, abl, [a, ab al}. We do not include EOS in A for simplicity.
Finally, we note that one can efficiently search for all elements within this set with linear time complexity O((ev,r.l) by leveraging the valid encoding condition [ For details, see Appendix
CROSS- CROSS-TOKENIZER LIKELIHOOD SCORING ALGORITTMS
This section provides a mathematical formalization of cross-tokenizer scoring (conversion) and presents the algorithms that enable this operation. The derivation of these algorithms makes essential use of the relative alphabet introduced Section 3.2
4.1 PROBLEM SETUP
Tokenier Scoring (Conversion). Let V. and 1/8 be two BPE vocabularies built over the same base alphabet. We consider language model Pv. trained with text tokenized under V,- Given encoding ēy, Vÿ. goal is to evaluate the probability, under Pv., of generating text whose Ve-encoding begins with ěv,- Formally, let Ee Pv. (.) be the (random) token sequence obtained by autoregressively sampling from Pv. until the first occurrence of an <EOS> token, i.e. e [-1]=<<0Oss and define the associated (random) byte sequence
X
decodey, (Cr)).
The conversion probability the prefix Ey₁ is then
Pv. (@v,) A Pr Prfencodev, (x) begins with ēv,]
5

---

Published as a conference paper at ICLR 2026
That is, Pv. (ēv,) denotes the probability that sample from Pv.. after decoding to its underlying byte sequence and re-encoding under Va, has εy, as prefix.
In the conversion task, we would like to express Pv. (Gv,) as a functions f of Pv. (C..v)) for i == 1,2,... where V. E V/ are encodings within Va in particular:
Pv. (6v,)) = ( (61.v)), (d.vv.. Pv. (62.v)......
where each term Pv. (e..v) is the standard autoregressive likelihood assigned by the model Pv. to the Vt-toeen sequence V. and can therefore be computed directly via single forward pass of the model. Once this representation is established, next-token probabilities can be obtained directly via Bayes' rule. We illustrate the nontrivial nature of this task with the following example.
Example 2. Let Pv., operating over vocabulary V== b) and the target (== b, a-b). Suppose 6y-=(o, a, b). if we compute Pv. (6v,)= )=Pv Pv, Pa, (bla, b) then we will end up with some positive probability if conditional probability is nonzero. This, however, is incorrect since the encoding εy = [, a, b] never appears the tokenized text distribution under V3. i.c. invalid encoding, and thus its probability is actually 0.0, i.e., tokenization bias in (Phan et al. 2025).
Algorithm Overview. Let Va be a BPE vocabulary and Vas 3 Vas be one of its subsets. We will describe in details two types of conversions:
Full-to-Subset Conversion: Converts a language model PM trained on VM to statistically equivalent model Par that operates on Var-
2. Subset-to-Full Conversion: Converts model PMr trained on VMr to statistically equivalent model Par that uses the full vocabulary VM.
For the general case with any pair of vocabularies Va and V3. we can:
1. Convert the model defined Va to its byte-level equivalent on Vo:
2. Convert the byte-level model on Vo to operate the target vocabulary V/3.
Combining the two scenarios, we can convert between any two BPE vocabularies V. and V that share the same base alphabet A. We summarize this whole framework in Figure
4.2 FULL-TO-SUBSET CONVERSION
Section
3.2 establishes that any subset vocabulary VMr can be viewed an alphabet of VM- Thus, now leverage the previous result from (Phan al. 2025). which converts tokenized LMs to byte-level (alphabet) LMs. In particular, we obtain the following conversion result that allows us to convert any model PV over VM Pv over VMr.
Lemma 1. Let VMr < VM with the based alphabet A, and let P(-) be a language model over any arbitrary vocabulary V with A V. Given a valid encoding εv over Var, the probability that the LM P(.) generates string whose encoding under VM begins with ēy is given by:
P(
Σ P(εvar)
EV
where C A cover the set of relative cover encodings in Definition 4
Proof. See Appendix B
From Lemma [ LMs defined over the vocabulary Var can be directly converted to operate on any nub-vocabulary Var by substituting P(.) with P.r(.). We conclude this full-to-subset conversion procedure with discussion the computational complexity of next-token sampling this setting.
Remark 1. Lemma I can be seen a generalization of the corresponding Lemma in (Phan al., 2025) by replacing VAY' = A. Furthermore, given that they share the same marginalization structure through the establishment of cover encodings, it is thus possible to perform autoregressive sampling with (1)) complexity in terms of model runs, allowing direct distillation for vocabulary trimming problems. For details, Appendix

---

Published as a conference paper at ICLR 2026
Algorithm 1: Recursive Vocabulary Conversion
Input: Encoding εy3, over vocabulary VM: language model defined over VMr 3 VM Output: Probability P(êv)) under P
Function ConvertProl (e, :):
if M = M' then
return (c)
Let tm t/f th Odec - decodeM--M-1(C))
be the token added at step M;
Calt Edec M
rrghht
if if + MM then
return ConvertProb (Édec, MM-1)
return ConvertProb (Edec, M 1) - ConvertProb (ēal: M-1);
Example 3. Following the setup in Example then we can express Pv, (la, ab]), i.e. the probability of encoding within Vi as the sum of Pv, ([a, abl) and Pv, (1a, abal).
4.3 SUBSET-TO-FURE CONVERSION
For this scenario, it is unclear whether similar direct marginalization is possible. Consider the problem of converting Vo VM, one idea perform the following marginalization:
Polévas) = Σ Pols Po(s-EOS) EOS) ( encodem(s [EOS)][ 1ev, ||}
(10)
where L = |dccoder- )I That is, we sum over the probability of the string ending with EOS, whose encoding under VM begins with desired prefix ēM. ranging over arbitrarily long sequences. Carrying out this marginalization requires enumerating such strings without any a priori stopping bound, prompting a question of whether there is a finite-time procedure for this conversion problem. Indeed, by again leveraging the sequential decoding structure, find that such a procedure exists and one can compute Po (e(e within finite enumeration. particular, we adopt incremental vocabularies
recursive construction approach and iteratively convert encodings where the conversion is tractable for each intermediate step. Specifically, let ev be an encoding from +1 and recall its construction:
VM Var append
where: t MM4+1
right MM411
(11)
Suppose the last token of ōv |-1] * tleft 'M'41 then we have the cover encoding set size |C]
in Equation (9 since there is no token VM can contain Ev except itself. Thus, let ēy decode (@v ). then we have:
(Mr(@vsr4)) Parr (Gv..))..)))
(12)
If Tōvv [-1]
left 41 then besides left "1'+1 we also have tM141 containing vV [-1], thus:
PMr (Mr(ev
Par (ev Par (ēv MM4+1>
right
(13)
and thus the recursion relation can be established, shown in Algorithm [ The correctness proof in Appendix and guaranteed to terminate finite time: each recursive call steps back to the immediately preceding vocabulary, progressing toward Vmr. Nevertheless, its worst-case cost (expp M M))) evaluations PMr, which is prohibitive. In practice, however, most leaves contribute negligibly because (i) well-trained LMs concentrate next-token probability on small subset of candidates, and (ii) the vast majority of leaf encodings are semantically or syntactically implausible and therefore receive vanishing probability. We thus prune the recursion by restricting to high-prun probabiity continuations and exploiting pre- pre-tokenization patterns. A complete description is in Appendix C.T with empirical results for approximation quality in Section 6.1

---

Published as a conference paper at ICLR 2026
Example 4. Following the setup in Example 1 say that want to compute Pvy (v,((a,,b) ab)). Running the algorithm step by step, we have:
1. Recursion at V2: since in V2, the token ab is part of the final token ab a, branch out:
Pv. (Ia, abl) = Pv, (Ia, abl) - Pv. ([a, ab,
2. Recursion at V1: since in V1, the token in the second term of the above equation is a part of the final token a b, we branch out again while keeping the first term intact:
Pus (1a, abl) Pvo ((a, a, bl) - (Pv (1a, a, b, al) - Pvo (lo a, a, a]]]] Pv (la, a, bl) Pv ([a, a, a,
Intuitively, there are four possibilities for the next two characters of the string aab, namely aa, ab, ba and bb. Consider the string aabaa, can that, regardless of any continuation after, the first two tokens under V/2 is still [a.aba] due to the last character a acts as a buffer guaranteeing the merge for token aba. For the string aabab, the last character b prevents the merge of aba and thus guarantee to form the desired encoding [a, ab]. Finally, the strings aabba and aabbb must have [a,ab] as the first two tokens under V2, thus consistent with final result.
RELATED WORK
Cross-Tokenizee Sampling and Scoring. There has been growing interest in sampling from language models under tokenizers different from the ones they were originally trained on. Phan al. (2025) introduce the concept of tokenization bias, explaining why tokenized LMS can fail to produce correct outputs when prompts end with partial tokens. They further propose an algorithm that converts tokenized LMs into equivalent byte-level models, achieving constant- time complexity
of (1) (model runs) for next-token sampling. Similar studies (Vicira et al. 2025a Hayase et al., 2025) also tackle this problem, using slightly different formulations and algorithmic techniques. Our work generalizes these prior approaches along two dimensions. First, whereas existing methods are restricted to conversions from full vocabulary to the byte-level alphabet A, our formulation in Section 4.2 applies to any subset vocabulary V. < Var. Building this formulation, we further develop algorithms for the cross-tokenizer conversion setting, see Section 4.3 enabling conversions between arbitrary pairs of BPE tokenizers. To the best of our knowledge, existing results for this setting have only been partially explored in [Phan et al. (2024) for maximum- encoding, which has been largely replaced by BPE. Second, the level of analysis, we introduce new technical tools to characterize such conversions; e.g., the notion of relative cover encodings (Definition 4
generalizes the cover encoding of Phan et al. (2025) beyond the byte-level vocabulary A.
Cross-Tokes Tokenizer Distillation, Cross-tokenizer distillation seeks to transfer knowledge across models built on distinct vocabularies. Prior work (Boizard al., 2025 Cui al. 2025 Feng
et al. 2024) has approached this by applying optimal transport to align teacher and student supervision. A complementary line (Wan et al. 2024 Minixhofer et al. 2025] Chen et al.) 2025) instead reduces distributional divergence by approximating marginalized probabilities through sequence alignment. Ultimately, these methods either impose strong assumptions on the logit representation or rely on heuristic approximations of sequence likelihoods. In contrast, our framework derives directly from first principles: we develop probabilistic formulation that computes exact sequence likelihoods under arbitrary BPE vocabularies, enabling lossless and principled cross-tokenizer distillation.
logits, thereby providing vocabulary-agnoste
EXPERIMENTS
6.1 COOSS-TOKENIZERR DISTILLATION
Approximation Quality. We begin with validating the approximation scheme mentioned in Section 4.3 In particular, we convert the Dwwen..5-7BIInstte model to its equivalent bete-level model using the Hull-to-Subset procedure, where the whole alphabet with (1) complexity. We use this byte-level probabilities from this converted model to re-compute the next-token probability of the original Qwen2.5-7B Instrrcct model using
compute the next-byte probability over
8

---

Published as a conference paper at ICLR 2026
1.0
Method
Accuracy (5-shot)
Gemma2-2N8 BB--truttttt (Student) 1ran2.5-Math-775 I-Instrruct (Teacher)
52.3
88.4
Orignol
0.-
SFT
47.9
ULD Boizard et al. 2025
47.1
ULD SFT Boizard el al.
2025
48.2
DSKD
Zhang et al.
2024
51.5
DSKD
SFF Zhang et al
2024
52.8
0.3
ALM
53.2
ALM + SFT
53.5
Dleal
PKL (Ours)
54.6
0.0
0.2
0.4
086
0.5
1.0
SFT + PKL (Ours)
55.6
Approcination (RMSS
0.015)
Figure 4: Empirical approximation of next-token probabilities.
Table 1: GSM8K distillation (Qwen2.5-Math-7B -> Gemma2-2B).
the approximation process in Appendix C.I Figure shows the approximations closely match the token-level ground truths, confirming the correctness of the proposed method. This beam-search approximation amounts evaluating approximately beams, each with an average length of 10, and takes roughly 0.5 seconds per next-token evaluation, i.e. unlike the Full-to-Subset case, we only get the probability of one query token instead of the whole distribution over the subset vocabulary.
Distillation Results. We train and evaluate cross-tokenizer distillation on GSM8K using Swten2.--Mtth-7B--
(teacher) and Gemma-2-2B: Instructt (student), chosen for their minimal vocabulary overlap. For each prompt, we score five tokens: the ground tround-truth, the student's 's top- 1, and three additional candidate tokens obtained via beam search; see Appendix C.I Training minimizes a partial Kullback-Leibler divergence (PKL) (weight w, see Equation (35) in Appendix D plus a sopervised-finttunee (SFT) term (weight 1 w); use PKL instead of forward KL because only a small subset of (1 to 5) token probabilities performed teacher inference offline, generating soft labels for 7,500 training examples. We show results for w E {0.0, 0.8, 1.0} (pure SFT, validated mix, pure PKL) and compare against Approximate Likelihood Matching (ALM) (Minixhofer al., (024)). the current state of the art for cross-tokenizer distillation. Models are trained end-to-end (without LoRA), using a batch size of 64 and learning rate of 10-6 6 Table shows our method outperforms others and achieves the best results when combined with SFT. Notably, our approach strictly generalizes ALM: it recovers ALM in the limit of ALM chunk size with )peree) debiasing, while additionally leveraging probabilities of aon-ground-trthh tokens. See Appendix D for results translation task.
available. To minimize training-tine computation,
6.2 VOCABULARY TRIMMING
We study the performance of approach for the Hull-to-Subset conversion in the vocabulary trimming problem, i.e. to decrease the memory footprint of its language modeling head. We evaluate our method's performance on domain-specific reasoning tasks, including arithmetic reasoning and coding, alongside with multiple general-purpose reasoning tasks in Appendix E
Setup. We utilize the model as the base for the student model, with an original vocabulary size of 151, 643, and truncate to the first {16, 32, 64} 103 merges. For both domain-specific and general- purpose reasoning tasks, we initiate a warm- up distillation phase for one epoch on the Alpaca dataset (Taori et al.) 2023), which contains approximately 50,000 instruction- following examples, using the Qwen2.5-77- Instruct model as the teacher model. The primary goal is to enable the student model to redistribute probability mass over its reduced vocabulary. We compare performance with 0.0 (pure SFT), 1.0 (pure distillation), and
Vocab Size
LMH
LM Memory
Saved
16k
45 MB
2.48GB
13.5%
32k
91 MB
2.53GB
12.0%
64k
182 MB
2.62GB
9%
151k
445 MB
2.88GB
0%
LMH LM head memory.
Table 2: Memory impact of vocabulary trimming (bfloat16).

---

Published as a conference paper at ICLR 2026
GSM8K (4-shol Acc)
HumanEval (D-hott
MBPP (3-sbot)
Vocab
SFT
FKL
ALM
ULD
DSDK
SFT
FKL
ALM
ULD
DSDK
SET
FKL
ALM
ULD
DSDK
53.2
56.5
51.2
52.1
42.6
28.6
30.5
30.8
32.2
33.3
(w/
53.6
54.3
46.4
32.3
41.4
33.1
34.2
32k
54,0
58.6
57.1
53.5
54.4
46,9
47.6
32.3
30,5
40.2
38.8
41.8
35.6
33.5
34,6
(w/ SFT)
63.0
61.1
57.1
59.3
47.6
39.6
34.1
41.4
40.6
33.4
32.2
36.0
55.5
57.3
51.8
32.3
42.6
34.4
37.0
(w/ SFT)
58.4
51.2
36.1
43.0
36.4
35.2
38.7
Full Vocab
60.2
61.1
57.0
58.1
49.4
50.6
42.6
48,7
42.0
43.0
39.9
41.2
(W/ SFT)
63.2
62.1
52.4
48.2
43.4
42.4
Table 3: Performance GSM8K, HumanEval, and MBPP (pass@) 1). Columns report SFT. FKL (our method, with/without SFT), and the baselines ALM (with/without SFT), ULD and DSDK. In the Full Vocab row, the blue entry (ULDD column) denotes the original model's performance, not ULD score. Our method consistently improves accuracy under the vocabulary trimming setup.
set w = 0.8 for the combined loss after validation sweeps. Following warm-up, for mathematical reasoning. we distill the student for two epochs on the GSM8K training split (Cobbe er al.) [00TT) using Qwen2.5-Math-77 7B-Instruc as a domain-cxpert teacher. For the coding task, we distill the student models on the OPC dataset (Huang et al.] (024), employing the Qwen2.5-Coder-77 -anst-eB-Instruuct model. To minimize on-the-fly computation, we perform teacher inference offline and store the top-K K probabilities for distillation, with K = 20.
Results. As shown in Table 3 our alignment method, consistent with the cross-tokenizer distillation setting, outperforms baselines by utilizing a well-aligned distillation objective. The distilled models maintain strong performance despite reduced vocabulary sizes. On GSM8K, the 32k variant improves over the original by nearly 5% and surpasses SFT by approximately 9%, while reducing the memory footprint by about 12%. These results highlight the advantages of our algorithm and perfect sequence alignment for this problem.
7 CONCLUSION
This paper shows cross-tokenizer scoring algorithms that compute sequence likelihoods for any BPE encoding, regardless the language model's native tokenizer, with finite time termination. For scenarios where the target vocabulary is a subset of the model's vocabulary, our approach delivers exact likelihoods and supports sequential sampling with only ((1) model evaluations per token. For arbitrary vocabularies, we propose lossless method that leverages BPE's recursive structure, alongside a fast approximation designed for large vocabularies. Experimental results confirm robust cross-model knowledge distillation across incompatible tokenizers, underscoring the versatility and precision of our algorithms. Future work will focus on optimizing the general-cass algorithm and its approximation by reducing time and memory demands through techniques such enhanced pruning or beam search. Moreover, our approach's 'ss flexibility, which avoids intermediate steps like sentence alignment used in other methods, makes it particularly well-suited for modern distillation techniques, such as on-policy distillation (Agarwal et al.) 2024). Related problems also include cross-tokenizer preference optimization where the verifier can only output reward for specific token. Another promising direction involves applying our method to tokenization adaptation (Zheng al. 2024), where we anticipate significant performance improvements in downstream tasks and target domains, further amplifying the practical impact of our algorithms.
ACKNOWLEDGMENT
Resources used in preparing this research provided, in part, by the Province of Ontario, the Government Canada through CIFAR, and companies sponsoring the Vector Institute www.eectoinssinuc.a//aarerrsssii
10

---

Published as a conference paper at ICLR 2026
REPRODUCIBILITY STATEMENT
To ensure transparency and reproducibility, we will release all artifacts required to replicate our results, including environment specifications, training/evaluation scripts, and code.
STATEMENT ON THE USE OF LARGE LANGUAGE MODELS
We did not use large language models for any part of this paper (including experiments, analyses, proofs, or writing). All conceptual contributions, study design, implementation, and writing were carried out by the authors.

---

Published as a conference paper at ICLR 2026
REFERENCES
Rishabh Agarwal, Nino Vieillard, Yongchao Zhou, Piotr Stanczyk, Sabela Ramos Garea, Matthieu Geist, and Olivier Bachem. On-policy distillation of language models: Learning from self- generated mistakes. In The twelfth international conference on learning representations, 2024.
Nicolas Boizard, Kevin El Haddad, CELINE HUDELOT, and Pierre Colombo. Towards cross- tokenizer distillation: the universal logit distillation loss for llms. Transactions on Machine Learning Research, 2025.
Yijie Chen, Yijin Liu, Fandong Meng, Yufeng Chen, Jinan Xu, and Jie Zhou. Enhancing cross-tokenizer knowledge distillation with contextual dynamical mapping. arXiv preprint arXiv:2502.11104 2025.
Yulong Chen, Yang Liu, Liang Chen, and Yue Zhang. Dialogsum: A real-life scenario dialogue summarization dataset. arXiv preprint arXiv:2105.06762, 2021.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint I 1 14668, 2021.
Marco Cognetta, Tatsuya Hiraoka, Rico Sennrich, Yuval Pinter, and Naoaki Okazaki. An analysis of bpe vocabulary trimming in neural machine translation. In Proceedings of the Fifth Workshop on Insights from Negative Results in NLP, pp. 48 18-50, 2024.
Xiao Cui, Mo Zhu, Yulei Qin, Liang Xie, Wengang Zhou, and Houqiang Li. Multi-level optimal transport for universal cross-tokenizer knowledge distillation on language models, In Proceedings of the AAAI Conference Artificial Intelligence, volume 39, pp. 33724-23732, 2025.
Zhili Feng, Tanya Marwah, Lester Mackey, David Alvarez-Melis, and Nicolo Fusi. Adapting language models via token translation. Workshop on Machine Learning and Compression, NeurlPS 2024, 2024. URL
Philip Gage. A new algorithm for data compression. C Users Journal, 12(2):23-38, 1994.
Leo Gao, Jonathan Tow, Baber Abbasi, Stella Biderman, Sid Black, Anthony DiPofi, Charles Foster, Laurence Golding, Jeffrey Hsu, Alain Le Noac'h, Haonan Li, Kyle McDonell, Niklas Muennighoff, Chris Ociepa, Jason Phang, Laria Reynolds, Hailey Schoelkopf, Aviya Skowron, Lintang Sutawika, Erie Tang, Anish Thite, Ben Wang, Kevin Wang, and Andy Zou. The language model evaluation harness, 07 2024. https:::t:///// :ttttt:::/zzendd.ooo wwwpoodddooorrrreeeeeooeeeoeeoee retp/ds.orrdddoooo /werrds11a100 1268660662222222
Jonathan Hayase, Alisa Liu, Noah A Smith, and Sewoong Oh. Sampling from your language model one byte time. arXiv preprint arXiv:2506. 14123, 2025.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge neural network. arXiv preprint arXiv 0, 2015.
Siming Huang, Tianhao Cheng, Jason Klein Liu, Jiaran Hao, Liuyihan Song, Yang Xu, J. Yang, H. Liu, Chenchen Zhang, Linzheng Chai, Ruifeng Yuan, Zhaoxiang Zhang, Jie Fu, Qian Liu, Ge Zhang, Zili Wang, Yuan Qi. Yinghui Xu, and Wei Chu. Opencoder: The open cookbook for top-tier code large language models. 2024. URL http://////axx..oo//////////////
04905)
Benjamin Minixhofer, Edoardo Maria Ponti, and Ivan Vulić. Zero-shot tokenizer transfer. arXiv preprint arXiv:2405.07883, 2024.
Benjamin Minixhofer, Ivan Vulić, and Edoardo Maria Ponti. Universal cross-tokenizer distillation via approximate likelihood matching. arXiv preprint arXiv:2503.20088. 2025.
Buu Phan, Marton Havasi, Matthew Muckley, and Karen Ulirich. Understanding and mitigating tokenization bias in language models. arXiv preprint arXiv: 16829, 2024.
Buu Phan, Brandon Amos, Itai Gat, Marton Havasi, Matthew J. Muckley, and Karen Ullrich. Exact byte-level probabilities from tokenized language models for FIM-tasks and model ensembles. In The Thirteenth International Conference on Learning Representations, 2025. URL https:
//openrevien ew. net. www.:tttttttittttoo wot.orrwwmmmiiiiieee222222c..
12

---

Published as a conference paper at ICLR 2026
Tiago Pimentel and Clara Meister. How to compute the probability of word. arXiv preprint arXiv:2406. 140661 2024.
Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural machine translation of rare words with subword units, arXiv preprint arXiv:1508 A0V.00900.. 2015.
Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song. Xiao Bi, Haowei Zhang, Mingchuan Zhang, YK Li, Yang Wu, et al. Deepseekmath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03300, 2024.
Haebin Shin, Lei Ji, Xiao Liu, and Yeyun Gong. Overcoming vocabulary mismatch: Vocabulary- agnostic teacher guided language modeling. In Forty-second International Conference Machine Learning, 2025.
Chaofan Tao, Qian Liu, Longxu Dou, Niklas Muennighoff, Zhongwei Wan, Ping Luo, Min Lin, and Ngai Wong. Scaling laws with vocabulary: Larger models deserve larger vocabularies. In The Tiiht Annual Conference on Neural Information Processing Systems, 2024. URL
net. (aerrummmd=aKKKPP-ee BCRRI
Rohan Taori, Ishaan Gulrajani, Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto. Stanford alpaca: An instruction-folloinng llama model. petpss//githull wwwtthhw..omtttteeeeeeeeeeeeeeee wwwoo/tats-uaaae 1ab/ wtt.ssrrdoordaaaacccoc 2023.
Asahi Ushio, Yi Zhou, and Jose Camacho-Collados. Efficient multilingual language model compression through vocabulary trimming. In Findings of the Association for Computational Lingnistics: EMNLP 2023, pp. 14725-14739, 2023.
Tim Vieira, Benjamin LeBrun, Mario Giulianelli, Juan Luis Gastaldi, Brian DuSell, John Terilla, Timothy J O' Donnell, and Ryan Cotterell. From language models over tokens to language models over characters. In Forty-second International Conference on Machine Learning. 2025a.
Tim Vieira, Tianyu Liu, Clemente Pasti, Yahya Emara, Brian DuSell, Benjamin LeBrun, Mario Giuliamelli, Juan Luis Gastaldi, Timothy J O' D'Dnnlll,, and Ryan Cotterell. Language models over canonical byte-pair encodings. In Forty-second International Conference on Machine Learning. 2025b.
Fanqi Wan, Xinting Huang, Deng Cai. Xiaojun Quan, Wei Bi, and Shuming Shi. Knowledge fusion of large language models. arXiv preprint arXiv:2401.10491, 2024.
Wenda Xu, Rujun Han, Zifeng Wang, Long Le, Dhruv Madeka, Lei Li, William Yang Wang. Rishabh Agarwal, Chen-Yu Lee, and Tomas Pfister. Speculative knowledge distillation: Bridging the teacher-student gap through interleaved sampling. In The Thirteenth International Conference Learning Representations, 2025. URLhttps:/ http:///pppeeeeee...eee. wttp:vviwwweee/oruur.tee idd=EgJhwYR22B
Yongcheng Zeng, Guoqing Liu, Weiyu Ma, Ning Yang, Haifeng Zhang, and Jun Wang. Token-level direct preference optimization. arXiv preprint arXiv:2404. 11999, 2024.
Songming Zhang, Xue Zhang, Zengkui Sun, Yufeng Chen, and Jinan Xu. Dual-space knowledge distillation for large language models. arXiv preprint arXiv:2406.1733 2024.
Mengyu Zheng, Hanting Chen, Tianyu Guo, Chong Zhu, Binfan Zheng. Chang Xu, and Yunhe Wang. Enhancing large language models through adaptive tokenizers. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https://
13

---

Published as a conference paper at ICLR 2026
Algorithm 2: Relative Cover Encoding Search
Input: Encoding Gar over vocabulary VMr; target vocabulary VM: (ēy VM)
Function
cover dict = {
= decodo M' -+ 0)
for i +
do
#Find all tokens with prefix sli :] and tokenize s/: i B= {t Var (Eprefix(decode(()) 1|:0 - VM)
left tokens = encode(s|: #Filter only valid tokens for right_token E B do
s' decodeeleeft.tooeeee tokenns right.token) checkl = is valid
right.token)
11
check2 is equal i ; 0- M*) [: @y
13
if check1 and check2 then
cover wwterrdict.oo booet..dd(lof. (cft.tttoo tokens right.token)
15
return cover dict
A EFFICIENT NEXT-TOKEN SAMPLING FOR FULL-TO-SUBBET CONVERSION
A.1 RELATIVE COVER ENCODING
We begin by recalling the definition of relative cover encodings.
Relative Cover Encodings Let Vw N VM, and let ēu be valid encoding the vocabulary VM We say that an encoding ēv over VM is a relative cover encoding of ēv if the following conditions hold:
1. There exists sequence X such that ēy encode(X; M)[: jēv l1.
2. There exists an index i S jēv such that:
decode (1:Ev>,, 1]) Ev [1: 1},
Ty [d:] E prefix (decodeas-ad (ōv.,, [-1])
i.c. the last token of ēyy, starts from some location within e'y
In BPE, any Gys, must be valid encoding according to the first condition. Algorithm leverages this by first converting ,y to its string form Because the final token of a valid cover must match a suffix of we traverse s left-to-right: each position select the candidates right_token token Vas whose decoded string is prefix of slit], and concatenate it after left ftoees encode to form candidate cover. We then set s' decode(left. tokens right. token), re-encode s' under the aub-vocabulary to obtain eyy, f- encode(s'; 0 + M'), and verify that the resulting encoding begins with Gy
A.2 NEXT SUB-TOKEN SAMPLING
In this section, we focus computing the next-token probability for the subset vocabulary VM using the LM operating on the original vocabulary V. i.e. (- similar to the next-byte sampling procedure in (Phan al. 2025). We assume that we have access to:
1. The set of (relative) cover encoding and the corresponding probabilities of ēar: |- i.c. exclude the last token, obtained either from Algorithm or from previous sampling call (to be shown).
--1] 1],
2. The conditional next-token probability distribution PM |encode (M j 1))), obtained via previous model inference call.
14

---

Published as a conference paper at ICLR 2026
We define the following indicator function for the event that the token t VM begins with the sub-token t' E Vss through the decodeM-MM' operator.
1, if dr t',
ttt VM Vi > 1), t(t,t) &
(14)
otherwise,
We can proceed the sampling process through the follow 2-step procedure:
Step 1 (Relative Cover-Encodings Construction). We construct the cover encoding of ēыr by:
1. Remove the encodings in cover @ 1]] whose last token does not begins with the sampled sub-token (-1], i.e. T T e [ = We call this set Cnew.
2. Add the valid encodings (Mc [ @ 11) t for any tokens t in VM that begins with the sampled sub-token Cur [-]] i.. r(t, exr l [-1] = 1, in Cuew-
The resulting set Cnw thus is the desired cover(ee::).
Step (Compute Conditional Distribution).
To sample the next token l' E VM according
Par (-lēMr), we note that:
(es t') PMr (CM " t') = + PM (ŌM t', 5(0M +t) = 0), (15)
where 8(0M t') 1 if the sub-vocab encoding Eur E docodes (C'rs) where è M
cover(ēx:) and vice versa. In other words, it is an indicator function whether the sub-vocab encoding is contained within one of the cover encoding of ēa, Note that the first term is the sum of all cover encoding probabilities that satisfy the indicator function propenty.
For the second term, we have:
(a t', 6(ēar t') 0)
(16)
(t Var starts with E Iencode>' (ēwr) Pa (e (xcodees->((w>>))
(17)
where the first term in the product the model evaluation step need to and the second term is already computed from previous cover encodings step. We note that computing the first term in Equation (17) can be done in parallel. In particular, we can pre-compute the fixed prefix matrix
R Tx where:
Qic,1 = f1, ff1,
if = Var is prefix of t = VMrli,
(18)
0, otherwise.
and thus for the sub-token t' [i]. we have:
Pas (t E Vas starts with d' (C.s))
(19)
Q Par (t/encodew/-pd/ ((.. (eww)))(
(20)
where Par( ( (a-leenode(@srr: M' + M)) can computed one inference round. Thus this sampling
procedure requires only inference step per next token. We show the whole procedure in Algorithm
B PROOF OF LEMMA
Lemma 1. Let VM VM. and let P(-) be language model over any arbitrary vocabulary V with A C. V. Given a prefix encoding ey over VMr the probability that the language model P(.) generates string whose encoding under Var begins with ēv., is given by:
P(ev
Σ )(ev.),
(21)
EV EC
where C é cover is the set of relative cover encodings in Definition
Proof. This result follows as a corollary of the Byte-Token Representation Lemma in Phan et al. 2025), where the vocabulary VAr is treated as relative alphabet with respect to VM- The sunmation over the cover set arises naturally from marginalizing over all tokenizations VM that map to the same decoded prefix under Var, established in Section 3.2 3.2
15

---

Published as a conference paper at ICLR 2026
Algorithm 3: Sampling Next Sub-Token
Input:
Encoding ear over vocabulary VMr target vocabulary VM:
Relative Cover Sets {(c, p.)) cover (@v [: | 1]} (including the
probabilities for each cover c;);
Conditional distribution Prond PMr(: encodew ēxr 1)))
Function
Samplingg (ēv,.: VM, ((c, Peoud
Step 1: Relative Cover-Encodings Construction;
coverM'->> (V) +
ion( VM, {(es, pi)}: p))nd(.));
Step 2: Compute Conditional Distribution;
// Note: encodeer Pa
cover ((
Puext() (+) t PM (e Pas--P (eeeodddes--M (M
for (c,p) E ( do
u' f decodeM-MM (c) Car
t' + u'10];
Pnext [t'] + Pnext [t'] +
10 Puext (.) < Pnext (-)/ Σ Puext (-);
Sample next-token l' Puext (:);
12
return p(-), (over
13
Function Cover_Construct on (6 VM, ((t.p:)), Peona()))
// Recall: ( @ar - 1]) {(G, pi)}
Cnew + {};
14
for (c,p) E MM (Gv, je 1]) do
15
17
T(l, 1- = then
L Cnew C.ee..appente append
bM + encoderr-(@@wr! | - 1]);
19
for Vas such that rtt, [-1) and valld f) do
20
21
ÿM + bm t;
(M = Peond (b [4]:
22
Cnew Shew.append((A)) PM ())));;
23
24
return Cnew:
C PROOF ALGORITHM
To prove the recursion step, we characterize the transition between adjacent vocabularies. Lemma 2 (Adjacent Vocabulary Transition). Let VM 3 VMr+1 be adjacent vocabularies, and let PMr (.) denote a language model defined over VMG Let @var4 be an encoding over VM and define its decoded form under VM as
Ty. = decode (x)
Let |M441
fleft 4/
right M4 be the token added in VM Then, the probability of ēy under
Pao is given by:
Par (@var)
e Terrnll-11 + MM
PM (@vse)) PM (ēver
right MM+1
otherwise.
Proof. Consider first the case where @y [-1] # fleft
11111 In this case, the relative cover set is
cover
(ēv (ey
16

---

Published as a conference paper at ICLR 2026
since the last token ev [-1] is part of any merged token in VMr+1, including tM Hence, the probability under Par remains unchanged:
PM (Ov Pas. (ov
Now consider the case where Gy Ar [-1] =
fleft
41 In this case, the relative cover set becomes
M' ( (var Ovar= [1( t
Applying Lemma ! which decomposes the marginal probability over all possible relative cover encodings, we obtain:
Par (ēver))))))== (Mr((Ev - PMs (1:::_/ (M
(22)
- Pasi (Gvms
tright +1
(23)
where the second equality is due to the previous case, i.e. 1 F dlftt token in VM This completes the proof.
M1 is not part of any other
Finally, given the result in Lemma 2 the recursion step in Algorithm follows naturally.
C.I SCORING AND SAMPLING WITH BEAM-SEARCH
Approximate Scoring Procedure. We focus on the conversion case from the byte-level model
Vo A to target vocabulary VM, denoted simply V. Let é be an encoding in V with string we have
representation s decode(C). From the lossless Algorithm 1
(v(e) Po(s)
Po(s', SEER
(24)
where Po(-) denotes probabilities under the byte-level model, and Ω is the correction set returned by Algorithm [ Each (s()') represents the probability that a sequence begins with prefix s'. Since evaluating the full set Si is generally intractable, goal is to approximate the correction term Eveg Po(s') by identifying a restricted collection of candidate strings that capture the dominant contributions, without explicitly enumerating all elements of Ω. First, observe that
Po(s) = P(sequence starts with s and matches é) + P(sequence starts with s but not é)
(25)
= Pv) + P(sequence starts with s but not ei,
(26)
and hence
(e = Ps(s) - P(sequence starts with s but not e).
(27)
We now make the following approximation:
P sequence starts with but not é) Σ P(s),
(28)
s'Ell
where:
II (s' starts with 8,
(29)
s' 1[[11] is the first white space/EOs appears after prefix 8, encode(s') [a]] * é)
(30)
(31)
This assumption is not overly restrictive. particularly for languages such as English where whitespace is frequently used. Intuitively, asserts that a continuation s' of is more likely to correspond to valid "word" rather than an arbitrary long character sequence. Moreover, under the standard pre-tokenization rule in which whitespace appears only at the beginning of a token, once whitespace is sampled, we can uniquely determine which encoding of s' follows up to that point g
RRadeer may find this resembles- though is not identical to-the process of computing the probability of word (Pimentel & Meister 2024
17

---

Published as a conference paper at ICLR 2026
Combine all the terms, have the following approximation for Pv(e):
Pv(č) Po(s)
Σ P(s)),
(32)
S'ETT
We summarize the procedure in two steps. Assume access byte-level LM Po(-) (given obtained via conversion), and let č denote the target encoding.
1. Beam-search: Starting from Po(.ls). generates N candidate beams $1....'' using beamsearch until seeing whitespace/EOS.
2. Return: (v( x Po(s) Ever P(s').
Sampling a new token. Given a byte-level language model Po and current encoding č, we perform byte-level sampling autoregressively until stopping criterion is met (whitespace maximum length of cover encoding, ...). Let be the sampled string and encode(s) its tokenization under V. If encode(s) begins with é /. for some / V. output I; otherwise, reject and resample without recommitting to that path.
D DISTILLATION LOSS
We employ the following two distillation objectives for transferring knowledge from a teacher language model Ltacherr to a student model Pstuddnt- our experiment, we find that combining distillation loss with the SFT loss gives better results.
Per-token KI. Distillation (Hinton al., 2015). Following the standard distillation framework, the teacher provides full predictive distribution Preacher( I<ee) over the student vocabulary V Vstudent A V. The student is trained to minimize the token-wise Kullback-Leibler (KL) divergence between the teacher and student distributions:
L
CKL
Σ
DKL Preacher x<<e) Pstudent (x<e))
(33)
Em1
1.
Patudent (f x<(e Preacher(1 xiee) log
= = Σ Σ
(34)
Preacher (b x<ee)
[=1EE
This loss encourages the student to match the teacher's complete predictive distribution at every position. It is particularly suitable for the sub-vocabulary distillation problem since we can obtain the probability distribution over the student vocabulary in ((1) model inference.
Partial KL Divergence Loss. In general, cross-tokenizer distillation, obtaining the full probability distribution over the vocabulary is impractical due to the time-intensive process of calculating each token's 's likelihood (approximately 0.5 seconds per token). In our approach, we typically compute probabilities for about three cross-(next) tokens per encoded prompt, leaving a significant portion of the probability mass unexamined. For this reason, we adjust the above KI. divergence loss to take into account the unknown probability mass. In particular, we optimize:
Lbin Σ (=1 tEQ(F)
Σ
a log Ps(u xxee) (1 (1- Σ qe) log (1- Ps [xee))] (35) (EQ(E)
tEQ())
where Q(E) is the set of random tokens in V sampled at step by the teacher. In the case Q(!) contains only the next token in the corpus, this recovers and generalizes the binary cross entropy loss in (Mimihoofer et al. 2025), without employing the sequence alignment step.
18

---

Published as a conference paper at ICLR 2026
Vocab
Task
SFT
FKL (Ours)
FKL (Ours)
ALM
ALM
ULD
ULD*
DSKD
DSKD
ARC-C
46.5
46.5
46.9
4644
46.3
45.1
46.2
45.9
46.3
ARC-E
72.9
73.2
74.0
72.4
72.5
72.2
72.4
73.1
73.6
BOOLQ
78.2
78.9
64k
COMMONSENSE
75.1
75.2
75.4
75.3
74,9
75.3
75.1
74.7
75.2
Hellaswag
49.2
48.9
49.5
48.9
49.1
48.1
49.0
48.5
48.8
PIQA
75.2
74,9
75.5
74.5
75.0
75.1
75.3
72.1
74.9
ARC-C
43.2
44.4
43.3
42.4
44.2
43.3
44.0
ARC-E
71.2
68.9
71.6
67.7
68.6
66.5
67.1
69.9
70.2
BOOLQ
78.6
32k
COMMONSENSE
74.5
75.0
75.7
75.1
75.0
72.4
73.4
72.9
73.8
Hellaswag
47.5
47.2
47.8
46.9
47.4
46.3
46.9
47.1
47.5
PIQA
73.2
72.3
73.5
71.9
72.2
70.1
71.0
72.5
72.9
ARC-E
66.9
66.8
68.1
65.1
66.6
62.9
64.1
63.5
64.7
BOOLQ
78.1
78,9
78.6
78.6
72.1
72.4
72.8
73.6
16k
COMMONSENSE
74.7
74.3
73.8
74.4
74.3
70.1
70.3
71.0
72.8
Hellaswwg
45.4
45.3
43.7
44.9
45.2
40.1
42.8
41.1
43.8
PIQA
70.1
67.1
70.5
70.7
Table 5: Performance across vocab sizes common reasoning datasets, We use 4-shot prompting for all tasks and setups. denotes distillation loss function combined with SFT objective.
E ADDITIONAL EXPERIMENT
Evaluation Frameworks. All experiments, including the cross-tokenizer distillation, evaluated using the Im-eval framework (Gao et al. 2024).
Distillation. We additionally evaluate the general cross- tokenizer distillation setting on the Dim summarization dataset (Chen et al. 202T), following the experimental setup of (Xu et al., (225). DialogSum contains 12.5k examples; we use 10k for supervised finetuning of the teacher model
Method
ROUGE-L
Gemma (Student)
12.3
Qwen2.5-7B-IT (Teacher)
39.1
SFT
31.9
ULD Boizard al. 2025
28.1
ULD + SFT (Boizard
2025
32.2
DSKD Zhang
2024
30.3
DSKD SFT ZZhngg
2024)
32.8
1aemn2.577BIIsttne Ik for distilling the student model (Gemma-22 1-amma-233 2B Instruct) using the SFT finetuned teacher, with the remaining 1.5k for validation. This configuration reflects common low-resource distillation scenario. where only small student-side dataset available during knowledge transfer. During the distillation phase, train the student with batch size of for total of 325 steps (3 epochs) using a learning rate of x 10-5, Overall, we find that our approach remains competitive with existing techniques and achieves the highest summarization score, highlighting the generality and robustness our framework across tokenizer mismatches.
ALM
20,5
ALM + SFT
33.1
PKI. (Ours)
32.6
SFT + PKL (Ours)
33,9
Table 4: TokeniTe distillation (Qwen2.5-7B:
IT Gemma-20 2B- on the the DialogSum dataset.
Vocabulary Trimming. We report additional results on common reasoning benchmarks. In this setting, rather than fine-tuning on each target dataset (as in the GSM8K and coding experiments), we continue training on the Alpaca dataset for two more epochs and then evaluate on the benchmarks. The results is shown in Table where our method consistently outperforms the baseline methods on most benchmarks.
19


Reviews:
[{"review_id": "JEr1bGhJto", "reviewer": "Reviewer_oe8u", "summary": "This paper addresses the issue of cross-tokenization, which is of paramount importance in the context of LLM distillation. The issue arises from the vocabulary misalignment problem, often caused by different tokenizers used in various language models. The paper introduces a new approach to tackling this issue, known as cross-tokenizer scoring or cross-tokenizer conversion, which builds strongly on the structure of the BPE algorithm widely used in current tokenizers. \nThe paper introduces the following contributions :\n+ An analysis of the sequential structure of the byte-pair encoding and the introduction of the notion of relative alphabets.\n+ Cross-tokenizer scoring algorithms\n+ Experimental validation on two tasks: cross-tokenizer distillation and vocabulary trimming.", "questions": "+ What about cross-tokenization outside the BPE algorithm? \n+ Would it be possible to describe more explicitly what contributions the approach makes in relation to the work of [Phan et al., 2025.]? \n+ In term of practical applications, what brings the concept of relative vocabularies ? \n+ How can it be used more concretely in a KD context, for example? \n+ Why was the standard experimental protocol of [Minixhofer et al. 2025] not followed in the experimental validation?", "limitations": "", "rating": 2, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "**originality**\n+ The idea of cross-tokenizer conversion for LLM Knowledge distillation is original. \n+ The notion of relative alphabets.\n\n\n **significance**\n+ The questions being asked are important since LLM distillation, assuming different vocabulary, is a very common practical use case.", "weaknesses": "+ The proposed approach is primarily limited to BPE tokenization algorithms. While it is true that many current tokenizers are built on BPE, it is not always the case. \n+ The clarity of the paper is clearly a big weakness of the paper. In particular, the proposed formalization is difficult to follow due to a lack of motivation or descriptions of the intuitions behind the concepts. For instance, section 4.2 is mainly a succession of definitions. In addition, some of the proposed definitions are generalizations of existing ones, such as relative cover encoding. Why is the notion of cover encoding important? A detailed positioning of the proposed approach with respect to the work of [Phan et al,. 2025] is also missing. There are certainly some very good ideas in this paper, but the format makes it very difficult to read and understand. It would have been interesting, for example, to consider a diagram highlighting the general framework of the proposed approach, particularly the concept of relative alphabets on which everything is based.\n+ Experimental validation also does not allow us to highlight this notion of relative vocabularies and how it impacts the targeted tasks: LLM KD and vocabulary trimming.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aHXMR4zNL9", "reviewer": "Reviewer_WYa8", "summary": "This paper presents a method to exactly convert BPE-vocab LM models to any subset vocabulary(eg. Byte-level) in O(1) model evaluations. Furthermore, the authors propose a (somewhat expensive) method to approximately up-convert the byte-level vocab LM to an obtain probabilities for any other BPE vocab. The authors show that their proposed vocab conversion achieves low approximation error in token probabilities, and can be used for cross-model distillation and vocab pruning.", "questions": "1. For Figure 3 (Section 6.1), can the authors share the effective LM loss (probability of ground truth token) for the original model and their re-converted model, and the LM loss of other smaller original Qwen models (no conversion needed) on the same samples? This can more directly show how much performance/\"effective model size\" is being lost in this conversion.\n1. In Table 3, for vocabulary trimming, can the authors also train the original (full vocab) model with the same warmup and distillation process? The vocabulary reduced models surprisingly achieve a \"higher\" score than the original models, while would imply the training process is significantly improving the model. Without these original scores, there is no way to judge the effectiveness of this conversion.\n1. For the beam search approximation in C1,  can the authors compare the quality of the predicted probabilities as the beam size is varied?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed method computes exact sub-token probabilities in O(1) model evaluations for BPE vocabs\n1. The proposed method is \"training-free\" on the teacher - requiring no training of new LM-heads, projections, etc\n1. The authors successfully utilize their method to distill across models and for vocabulary trimming.", "weaknesses": "1. The proposed method has extremely large overhead for cross-tokenization distillation - large number of beam-search (6-8 beams) upto maximum length 10 for calculating every token probability.\n1. Only 1 baseline method is compared against (ALM) - other methods for cross-model distillation should also be compared.\n1. Empirical evaluations are extremely limited.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wKuQ1u2E3w", "reviewer": "Reviewer_u4Tg", "summary": "This paper proposes Cross-Tokenizer Likelihood (CTL), a novel probabilistic alignment method addressing inconsistencies between multilingual tokenizers.\nBy minimizing per-token log-likelihood gaps across languages, CTL improves cross-lingual representation consistency and translation faithfulness.\nThe method is simple, elegant, and easily integrable into existing multilingual models (Qwen2.5-7B, XGLM-4.5B).", "questions": "N/A", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. Tackles a long-standing issue—tokenizer mismatch—using a mathematically grounded likelihood objective rather than architecture tricks.\n\n2. Improves multilingual alignment and reduces tokenization bias, especially for low-resource or morphologically rich languages.\n\n3. The CTL layer is training-agnostic and introduces negligible computational overhead.\n\n4. Consistent improvements across translation, code-switching, and QA tasks; simplicity and reproducibility make it valuable for practitioners.\n\n5. The loss function is interpretable and differentiable, connecting probabilistic alignment with linguistic intuitions.", "weaknesses": "Only three downstream tasks (translation, QA, code-switching). Additional domains such as summarization or retrieval would strengthen generality.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5cNv1TIovx", "reviewer": "Reviewer_c3nd", "summary": "This paper introduces cross-tokenizer likelihood scoring algorithms that enable language models trained with one tokenizer to compute exact or approximate likelihoods for sequences encoded with a different tokenizer by exploiting the recursive structure of Byte-Pair Encoding. The authors prove the merits of their methods through comparing against baselines on the knowledge distillation task.", "questions": "N/A", "limitations": "", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. This paper is addressing an important research question: how to compute next-token likelihoods and perform knowledge distillation when teacher and student models use different tokenizers (i.e., resolve vocabulary misalignment). \n\n2. The paper is well written.\n\n3. The paper’s idea is novel.\n\nI don't have the background to evaluate more fine-grained part of the methodology proposed in the paper.", "weaknesses": "I don't have the background to evaluate more fine-grained part of the methodology proposed in the paper. I will focus on evaluating the baselines.\n\nIn the experiment, the paper doesn't include the baselines for other methods that try to address the knowledge distillation problem with teacher and student sharing different tokenizers (e.g. those methods that align teacher and student on the level of embedding). I understand that the paper claims that it focuses on probability conversion on the tokenizer directly. However, in my opinion, unless the paper also show that their method is helpful in addressing some tasks other than knowledge distillation, other knowledge distillation baselines may need to be included. This is especially so when considering the fact this paper can only deal with the BPE tokenizer, while other aligning methods may deal with arbitrary tokenizers and models for the knowledge distillation task.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)