Lossless Vocabulary Reduction for Auto-Regressive Language Models
Authors: Daiki Chijiwa
Taku Hasegawa
Kyosuke Nishida
Shin'ya Yamaguchi
Tomoya Ohba
Tamao Sakao
Susumu Takeuchi
Venue: ICLR 2026 Poster (2026)
Keywords: Language Models
Next-Token Distribution
Tokenization
Vocabulary
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)

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.

Published as a conference paper at ICLR 2026
LOSSLESS VOCABULARY REDUCTION FOR AUTO-REGRESSIVE LANGUAGE MODELS
Daiki Chijiwa', Taku Hasegawa', Kyosuke Nishida², Saih'y Yamaguchi', Tomoya Ohba', Tamao Sakao', Susumu Takeuchi'
'NTT Computer and Data Science Laboratories, NTT Corporation NTT Human Informatics Laboratories, NTT Corporation
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.c., 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 cooperate with each other at the level of next-token distributions such as model ensemble. In this paper, we establish theoretical framework of lossless vocabulary reduction, which efficiently converts 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.
INTRODUCTION
Tokenization the process of decomposing given text into sequence of subwords called tokens plays an important role in modern language models (Schuster & Nakajima 2012 [ennrich et al. 2016 Kudo 2018). where tokens are the minimum unit for their input and output. Particularly, tokenization largely affects the efficiency of text generation with auto-regressive language models (Radford et al., 2019) which are trained to generate texts by first computing the next-token distribution given previous tokens and then sampling a token from it iteratively. In other words, the longer tokens are sampled at each iteration average, the less number of sampling iterations is required for text generation.
Each language model has its own vocabulary, the set of all possible tokens, which is generally constructed based on the statistics in their training data that more plausible texts can be represented by less numbers of tokens. As a result, given two (or more) language models that have been trained independently with distinct training data, their vocabularies do not match in general. Due to the vocabulary mismatch, language models with different tokenizers or vocabularies struggle to cooperate with each other at the level of their next-token distributions, such as ensemble (Hinton) 1999), knowledge distillation (Hinton et al. 2013). speculative decoding (Leviathan et al. 2023).
inference- time alignment (Mitchell et al. 2024), etc.
To this problem, recent work (Phan et al. 2025 Vieira et al. 2025) have proposed a theoretically- guaranteed approach that reduces a given next-token distribution to the corresponding next-byte distribution, without changing the distribution of generated texts. In other words, the resulting byte- level distribution is equivalent to the original toven-level one as probabilistic text generator, while its vocabulary being restricted to the set of all one-byte tokens, (0x00) to (OxFF). This approach enables language models with different vocabularies to cooperate with each other, at the level of their nett-byte distributions. However, the byte-level cooperation leads to increased inference costs by its nature, since each model has to predict byte by byte instead of tokens with multiple bytes.
In this paper, beyond the byte-level reduction, establish the first theoretical framework called lossless vocabulary reduction that reduces a given next-token distribution to the corresponding one over an arbitrary sub-vocabulary without changing its behavior text generator (Figure
"Correspondence Saiki .chi wa@ntt.com

---

Published as a conference paper at ICLR 2026
Language Model over V
My Py Hiue)
Propina
Japan 0.2
Pi-tran Otees 12te)
Eren Pr- Un "0
the
unit
10 003
Japansss u1
mus Os "M111 +)=
Py (0
China
(pust results)
Lossless Vocabulary Reduction
Pr- (1l11)
FiLe
0.3
of
boc in
|
thi witt
Jagan
Thlee Ioliin
Japan
Language Model over V
0.31
Kandian of Xeez Japanese
Tepanese
Figure 1: Overview of lossless vocabulary reduction. Instead of sampling tokens from the original next-token distribution over V. can inductively compute and sample from the equivalent distribu- tion over the sub-vocabulary Vsub while keeping its accuracy. See Section 3 for notations and details.
which is achieved by introducing the new notion of nested tokenization. Then we derive an efficient approximated algorithm to compute it with negligibly small overhead. As an application, we propose to cooperate language models with different vocabularies by lossless reduction to their maximal common vocabulary among them.
Finally, our contributions in this paper can be summarized follows:
1. We established the first theoretical framework of lossless vocabulary reduction and derived an efficient approximated algorithm that converts given next-token distributions over some vocabulary to the equivalent distributions over its arbitrary sub-vocabulary in inference-time. We also provided an illustrative example of how actually works following our theory.
2. Experimental results with several language models show that the derived algorithm is actually almost lossless as our theory suggests. Also, experimental results on ensemble show that ensemble the maximal common vocabulary achieves comparable accuracy to the byte-level ensemble while the former is more efficient than the latter.
2 PRELIMINARIES
Throughout this paper, we assume that any text is a sequence of bytes obtained by some character encoding. typically by UTF-8 (Yergeaul 2003). In this section, briefly introduce the formal definitions and properties of texts, tokenization, and language models.
2.1 FORMULATION OF TOKENS
Texts. Let A be set of symbols, such as all alphabets or all characters. Throughout this paper, A is considered as a set of all bytes, i.e., 8-bit strings b ...bg with by E (0. 13. Let AA" == U A U (0) = ... aN 0 A,N N) be the set of all finite sequences of bytes with an empty symbol O. We often use the notation a1NN == a....a.. aN for simplicity. Here we briefly note that (1) A consists of only 256 elements, obviously less than all symbols in the real world, (2) A consists of all possible texts in computers because they are represented by sequences of bytes.
Tokenization. A tokenization scheme T is formally detined as a triplet (V, [-lv. [I),), with finite set of vocabulary V. an encoder [-lv : A + V" and a decoder [-] 1" - A satisfying:
[(1::]y].c 01:N for all texts a1:N E A",, and [ = [m1] ... [DT]A for all tokens æ1.7 V*.
Each x called token in T. and has its textual representation [x]A E A given by the decoder. The encoder [-]y uniquely converts given text d1.N E A² to the corresponding tokens
J1.7 = [a..v]] with some length T. Note that the condition [1] has first appeared in Kudo & Richardson (2088) by treating texts as sequence of Unicode bytes such UTF-8 (Yergeau 2003
which is now employed by most of modern language models after Radford et al. (2019).
'The construction of A also known as the Kleene closure of A, and 0 means the empty string. Throughout this paper, we focus only deterministic tokenization which is widely employed in modem language models.
2

---

Published as a conference paper at ICLR 2026
2.2 FORMULATION AND PROPERTIES OF LANGUAGE MODELS
Language model over tokens. Let Prext (AINN) ) be the true distribution of natural language texts, defined over sequences of 8-bit binaries d1:N E A². A language model py(r):r), with respect to the tokenization T (V; I-lv, (-),) is defined as the probabilistic distribution over sequences of tokens 21.7 E V that matches the distribution of the encoded sequences [a1.v]y of natural texts a1.N Prext (A1:N). In other words, it is defined as
pv(E1:) = Prexi (aI:)), if #1.7 [aI.Nly for some (unique) a1.N E EA":
(2)
0,
otherwise.
Then say that (T(rT) is token distribution associated with the text distribution Ptext (a1:N):
Next-token distribution. From computational perspective, it is infeasible to implement the token distribution Pv(r1:r) directly. Rather, it standard implement its next-token distribution denoted as pv #1a-1), which we formally define here. First of all, let us introduce #1 Ti* 11 in shorthand, set of all tokens starting with x1 Z..:
Zz* {x1 244++1 zT V 24+17 V.,TEN, CV'
(3)
which plays a central role here. We can consider the corresponding probability to this event:
pv xx=)
pv(01 I,T441 TTTTT) IT)
(4)
21
Now the next-token distribution (2 111-11) is defined as the conditional probability
pv(
Pv( (1æ-1) = Pv(111* #14-1*)
(5)
pr(#La-1*)
We can sample a full sequence Z1r E V from the distribution py by recursively sampling Ty from the next-token distribution (y (1:4-1) starting from the empty string To 0. Hence, is sufficient to implement the next-token distribution (y x1.t-1) for the task of sequential text generation from (= Throughout this paper, we assume that the next-token distribution (xx T1a-1) ) can be computed for all I E V in parallel by single unit of computation, as an output of neural network followed by the softmax layer over the vocabulary V.
Valid tokens and minimal covering. Let T1.T y* be sequence of tokens. We call æ1.r is valid tokens if it satisfies the following inverse relation of Equation
[Iu.TAay = F1.T.
(6)
In other words, 21.7 is valid if and only it can be obtained by tokenizing some text d1:N, i.c., 21.77 =
[01:x] y- Indeed, in the latter case,
see æı. is valid since [[лıт]|)] [[[0::]] y]aay
[01:N] y = Fi.r by Equation {T). Obviously, if ø1:r is a valid tokens, is obtained by tokenizing
a1.N == [x AA the stringification of 11.7, clearly followed by Equation (6) Note that Equation (6)
generally does not hold solely by Equation ( and actually most sequences of tokens are invalid (Phan
al. 2024).
It is easy to see that the language model (v( associated with the true text distribution Ptext (01:N)
satisfies the following validity condition (Phan 2024
pv( = 0, for any invalid tokens Fi.r E V".
Indeed, by the above discussion, the invalid tokens Fi. never obtained by tokenizing any text a1:N. Thus the definition of (x falls into the second case in Equation
Importantly, the validity condition leads to simplification of probability computation for language models. To explain it, let us define the minimal cover Cy(ai:) for given texts d1.N by
Cy(a = i E 1* 0INN A [ anN < [FIT]A and æ1. valid.).
(8)
Note that this is not empty set because [d1.Nly E Cv(a ) always holds. Using this notion, Phan ctt al. (2025) and Vieira et al.) (2025) provided the following formula for computing the underlying distribution alphabets from the language model over tokens:
3

---

Published as a conference paper at ICLR 2026
Lemma 2.1
(Phan et al. (2025): Vieira et al. (2025) Let V be any vocabulary and py be the token
distribution associated with the text distribution Piext. For any string a1 $1.aa aN E EA,, we have
Prext (a1 aNx*)
E
ELTECC((LNN)
Since the minimal cover contains only valid tokens, the sum of the right- side will be com- putationally feasible, contrary to the case without the validity condition where the minimal cover may grow exponentially. particular, based on this formula, Phan et al. (2025) derived an efficient algorithm to compute the next-byte distribution Prexe (az (1:r-1) from the one over tokens.
3 LOSSLESS VOCABULARY REDUCTION
In this section, we establish theory and derive an algorithm to restrict the token vocabulary V of language model py((i:r to any given sub- cab-vocabulary Vsub, without changing behavior as a text generator. The theory and algorithm in this section will be leveraged for cooperation of language models with different vocabularies in the later sections.
3.1 FORMULATION OF VOCABULARY REDUCTION
Suppose that have language model py(r))), distribution over tokens in vocabulary V associated with the true text distribution Ptext (01.N). and denote its tokenizer Tv = (V, [-vv. [-la).
Nested tokenization. Let Vsub C be a sub-vocabulary, i.e., an arbitrary subset of the given vo- cabulary V, and V = (Vouh. -VsantI--vumn [-1a) be some tokenization scheme with the sub- sub-vocabulary. Here we do not necessarily impose any relation between [-]y and [-]v... except for the inclusion between the vocabularies.
Given such a tokenization scheme Tr... with the sub-vocabulary Vaub. we can define the nested tokenization TV-Vauu (Vsub, --ly-vauus [-la) that tokenizes text by applying [-]y and I-mm
[a1.N] V+Vee = [[a.:Nvllvvv... for a1.N E A", with
(10)
[2t v- (zyly-V.ns [zc]v-vemn. [[zs]alvmn for F1.T V",
where we abuse the notation [-]v- for denoting both [-]y-rv... :A" + V and [-]y-vv.n.* V" Vaub= as well as [-] for simplicity. The nested tokenization will play central role in our vocabulary reduction. If we consider the case of Vsub A and Ta = (A, id, the nested tokenization T just the stringification of given tokens.
Vocabulary reduction. Here we introduce new language model pv-Vuu (y1:k) over tokens in the sub- bob-vocayulaay Vsub. which is induced by the given language model py (x1:T) and the nested tokenization TV as follows:
Py-Ve. (2i:)) = EEarr-ooenr [1 = -Ii.rlv-v... = PPy): = [D1:rlv-vwa.: (11)
i.e. the probability that yı.k is obtained re-tokenization of æ1.7 V by the sub-vocabulary Vaub- We call py-vi.. (y)rk...(h:kk the vocabulary reduction of pv(#1r7) onto Vauh-
For example, if we employ the above TV-+ as the nested tokenization, the induced distribution py-A(a1NN) is nothing but the text distribution induced by the stringification of tokens I1.7 from (v(T).) Particularly, if (v(x1)) is associated with the true text distribution Ptext (01.N) we have
(V-A(( = F(a1.N = [ri. La) pv((a1:ll)) lv) Prext (Q1:N),
(12)
by Equation (2). Thus our definition of vocabulary reduction involves the previous byte-level reduction (Phan et al. 2025 Vieira al. 2025) as its special case with Vauu A.
Moreover, the vocabulary reduction Py-Vi.. is lossless. To see this, we consider the induced text distribution pV-V -AA (a)x),, ), i.e., the text distribution obtained the vocabulary reduction of Py-VVesh by another nested tokenization Trin By iteratively applying Equation we have
PV-V + -aassssaaaa (01:N) B -oux--p -V.m (0L (a1:N [91:k]A]]
4

---

Published as a conference paper at ICLR 2026
E mn [aaaiN [e
- [miTTla]
Pv-+A(1:NN)
By combining these equalities, we have proved the lossless property of vocabulary reduction:
Theorem 3.1. Let Prext be the true text distribution underlying the language model pv. Let us denote the text distribution associated with Vant by Py--Van A ). Then we have
PV-VVau + (a1:N) = AVV-A((NN)) = Prexe Puoxe(a1:N) (a1:N).
(13)
3.2 COMPUTATION OF THE NEXT-TOKEN DISTRIBUTION
At first glance, based on the above formulation, the computation of vocabulary reduction appears to be simple and easy at the level of probabilities over sentences, i.e., over V sub and V", But in reality, the probabilities over sentences are computationally infeasible the real world. Instead, we have to compute the corresponding next-token distribution Py-Vaut (V++1 | 91:k) over suu using the original next-token distribution py p2(+1+1 X1z) over V. Since the next-token distribution PV-Vaab (yk+1 V1:k) can be expressed as
PV-VVen (Us+1 V1:k) PV-+Voun (11+4+1+)
PV-VVou (11+411+)
(14)
Pv-Vaus (f1:2*)
Σ Ba41EV PV-Veut (11:k41*)
by its definition, the problem is how to compute the marginal distributions pe-Vaut (vI**)) To answer this problem, we introduce relative covering Cv.y (Vix), generalizing the minimal covering for V considered in Phan al. (2025); Vieira al. (2025) as follows:
Vv. (yi:k) = (I1: E V 11 is valid and satisfies yı:k < [Zislv-VVou
and y1.k A P1aa-ilv-Venl
(15)
Lemma 3.2. Let py and pV-Va be above. For any tokens yick E V", we have
Py-VVeu (V1:+*)
Σ
pv(11:*)
(16)
EL. (srok)
Proof. This a generalization of Lemma
See the proof of Lemma A.I
The next problem is: how to efficiently compute the right hand side of Equation 16 To answer this, we introduce the following subsets of the relative covering Cv, (V1.x):
Cee V.Van (ViSk) {x1 E CV.yaa (y1:s) [xIa)V- v1ck)
(17)
V.v.a (WIR) = OV.Van (VIVan((Vak) no {IL E Cv. (HIL) t t= 1}.
(18)
Then the summands in Equation (T6) can be decomposed into the following two cases.
Lemma 3.3. Fid E Vy (y1nk) if and only if Z1at satisfies either
(i) Fid E Cv.Van (V1:6-1) and yi:k x [21:1]] V-V
or (ii) F14-1 E Che V.Von (W1.-11) and xe E V.Vab (2k))
(!==1)
Proof. See the proof of Lemma A.2
Moreover, for the case (ii), we remark that the valid tokens #1 E C.) (V1=-1) can be uniquely
determined as T1:-1 [[vi=-=1lde 1laly for any valid" tokens V1:k-1. Indeed, if F1:--1 satisfies -1a-1Ip--y... = V1---1, we have [II = y - 1]4 and then F1a- = 1 = [1): by the validity of 1- Conversely, if 11 [1n*=1]4])
V1-4-1 with the valid tokens V1sk-1, we have [T1.c-I/v--... = - -llv-vvmml = y1.k by its validity.
By combining the above lemmas, we obtain the recursive formula compute the desired probabilities:
Herr consider the validity with respect TV-VVan i.e. (1lu---/lly-aus V1:k-1-
5

---

Published as a conference paper at ICLR 2026
Py Cit +)
Py (Ki (xx)
(0)
0.1
(0)
0.6
0.1
Sample = (00)
0.0
Eq.
(00)
(00)
22
(001)
0.3
Eq
Eq. 23
(001)
Py-PPeu O +)
Py-+ C'ad's
Py- 0% Y
(0)
0.1
= (0)
Normaize yi
(0)
0.375
(1)
0.1
Sample yo (00)
= (1)
0.3
0.375
(00)
0.8
(00)
0.2
y: (00)
Figure 2: Summary of calculation for our example with A {0, The upper part shows next-token distribution of the given language model py over V = {0)), (1), (00), (001)), }. and the lower part shows the derived vocabulary-rdducee model Pv-Vee over Vaub = {(0), (1), (00)}-
Theorem 3.4. For any tokens Vi:k E V that is valid with respect to the nested tokenization TV-+Vaab* we have
PV-Vauu (91a))(
E
pv(x +
Σ
Py(
(19)
Tua CVV. (D 1) st. gi.2 -[Fasslv-Voat
MF IF 100 (zn):
with 01:t- [b1
Proof. By Lemma 3.2 the left-hand side is expanded as the sum of probabilities p(x).c** over the relative cover 1ir Cy. Vau (V1:k). Then we know that each summand Taa satisfies either (i) (ii) Lemma 3.3 which leads to the decomposition shown in the right-hand side.
An illustrative example (Fig For simplicity, here we assume that A = f0, 1} instead of set of bytes. Let V = {(0). (1), (00), (001)} and V.ub == {(0), (1), (00000)); }. where each (-) denotes token. We suppose that the corresponding tokenizations are given by the greedy forward-matching tokenization, which maps each input bits b ... by E {0, 1 to the longest matching tokens in the
vocabulary, or Vaub greedily from left to right. Then we consider language model py over
given by:
0.1 if Fu (0),
0.6
if 21 (0).
0.1 zg = (I),
d = (1),
Pv(*o*)=
Pv(11 zo = (00))
(20)
0.5 if zu (00),
0.3 if 21 (00),
0.3 if (001).
0.1 if
(001),
Note that the tokens (00)(1) are invalid since 001 is tokenized (001) in the greedy forward- matching tokenization, and thus the probability pv(zi (1) xo (00)) is set to 0.
To compute Py-V (yo), we first calculate the relative covers:
Cy.yan ((0) (0)), Cv.v. ((1) {())) Ov. ((00) {(00), (001)),
(21)
Then compute the marginal probabilities Py-V (yo+) as
0.1 (= ()))))))
if yo (0).
Py-Ve. (20+) = 0.1 (= pv(())+))
if (1),
(22)
0.8 (= (
if yo (00),
Now suppose that yo (00) is sampled. To derive the next-token probability PV (v1 y/ (00)), we need to consider the following relative covers:
Cv.yon ((00) (0)) = { (00) Cy. ((00) (1) = {(001))
Cv. V.n.. ((00) (00)) ((00) (00), (00)(001))

---

Published as a conference paper at ICLR 2026
Algorithm Lossless Vocabulary Reduction.
Algorithm 2 Top-K Approximation. (K-LVR)
Inputs: Previously sampled lokens Mi E subs
Inputs: Same as Algorithm
global cache P for computed probabilities, a global cache C for relative minimal covers.
Outputs: Same as Algorithm
1: Tokenize Vı.k in V, i.c., 21. := I1..
Outputs: pv-Va.a (DK+1 V1:s) for gh+1 Vaub-
2: Compute ( for it E b/ a single
Tokenize Vi:k in V2 i.e., 2i: := Alvv.
forward computation, and store them in P.
Compute (2(2 for all in V/ by single forward computation, and store them in P.
3: Fetch Cv.y... (91.a) from the cache C.
4: for ya+1 E. Vaub do
3: Fetch Cv. (11.)) from the cache C.
5: Initialize Slye441] <- 0. D. for collecting probs.
4: for Ve-1 E Vaub do Initialize S Slye+1] 0. a for collecting probs.
6: Initialize Cy.y (yn:.-41) <- 0.
7: for di E Cy. (3/:a) do
Initialize Cy..e.a (vn.+1))))) 0. for d'L. Cv. (yL.) do
Me+1 + tte (A + 1)-th sub-token of #'. from the cache P. 10: Add zi to CryMiin (Wist+1)
8:
9: Fetch py(af
if 91-441 x (1 (ieelv-vvo. then
Fetch (2(tt)) from the cache P.
11:
Add py(a1:;"*) ) to S(ye41)-
10:
Add "i. to Cy. (21a41))
(X) <- {a E
(p((a1)))) within the top-K.) for #++1 E VVK) do
11:
Add po((11. S Ve-1l.
13:
12:
for Ge E do
14: Vk++1 + the first sub-token of [dre=aluaa
13:
if [2e=1lven. M6++1
Vuu then Add 21:++1 Cyn (1is++))-
15:
21.441 to (81.-1)) Add po(Z11 to S[Du+a]]
14:
16:
15:
Add (v
17:
for y-41 E Vaub do
16:
Store Vu. (B1:4+1) in the cache C.
18:
Store Cy.vaaa (1) the cache C.
17:
Set p(y++1) -ppssbu D. pa (11++1*))
19:
Set p(yk+1) <- [peS(pus) P. D Pv. W (4)))
18:
Set Pv, (3144 31ick) & p(y++1)/ Eg for all Me+1 Vauh-
Set pv,Vaa, (yE+11 (1:k) p(y++1)/ E, f(y)
Marginalization.
for all yk+1 E Vanh-
Marginalization
19:
return pV, V.s Miak)-
21: return Pv. (- (1as).
Then the marginal probabilities PV-vVau ((00) *) are obtained follows:
(0.3 (= (000 (0)+))
yı (0),
PV-VVau (100))1*)
0.3 (= (v((001)+)
yı (1),
(23)
0.2 (= (v00) (00)*) + pv ((00)(00)))) if (00),
Finally, we obtain the next-token distribution by normalizing the above marginal probabilities:
0.375
if y = (0),
PV-+Veu (y1 yo = (00)) = 0.375
if yı = (1). if y1 = (00),
(24)
0.25
We can easily check that the probability of the output text starts from "000" is 0.5 in both models py and Vy-VVen as expected by the lossless property (Theorem 3.I). For more details, see Appendix
3.3 ALGORITII
Based on our theory of lossless vocabulary reduction given the previous section, we derive an exact but computationally inefficient algorithm (Algorithm T and its efficient approximation (Algorithm) 2 for practical autoregressive language models.
Naive implementation. Based on the theoretical results in previous sections, we can derive an algorithm (Algorithm I to recursively compute and sample from next-token distributions PV- Venb over Veub, given only access to some autoregressive language model with the vocabulary V, i.e.. next-token distributions pv over V. Due to its recursive nature, we can suppose that sub-tokens Vi:k E Vaub have been sampled in previous iterations by this algorithm, and its intermediate outcomes properly cached. Under the circumstances, Algorithm [ computes the next-token distribution py-+V.u (yk+1 M1.k) for all y E Veub and sample a next token yk++1 from it.
Now we explain how Algorithm D produces the desired next-token distribution. First of all, the given previous output yı.k E Veub is re-tokenized in V. denoted by Z1. := [[vı= and then the next-token distribution pv( x1:)) is computed by the given autoregressive language model (lines 1-2). Note that here is the only part that requires access to the given language model in Algorithm and the results are cached in the global memory P so that they can be reused in future
7

---

Published as a conference paper at ICLR 2026
iterations. Then, in lines 3-17, the marginal probability Py-VVeu (31.491+++*) is computed for each 9k+1 E Veub by following Theorem 3.4. More precisely, lines 7-11 implement the first term in Equation [9 and lines 12-15 implement the second term. Finally, in line 18, the sum is normalized
over +1 E sub to obtain the desired next-token distribution according to Equation (14).
Efficient implementation. Algorithm | has naively implemented the vocabulary reduction based on Equation (16). Although the implementation is straightforward from the theoretical perspective, it computationally infeasible especially due to the two nested loops, lines 7-11 and lines 12-15. Here we discuss how deform Algorithm I into more efficiently approximated one, Algorithm 2
First of all, we consider the first nested loop (lines 7-11 in Algorithm D. which requires (eubll X
VCy-Vau (y1:k) iterations. This part can be separated from the outer loop over yk-+1 E Vsub, because the yk+1 satisfying the condition in the line 8 is uniquely determined as the (A: + 1-t sub-token of lv-glv-ve..s Thus we deform the lines 7-11 in Algorithm I into the lines 7-11 in Algorithm 2 which only requires |Cy=ven (31=x)] iterations.
Then we consider the second nested loop (lines 12-15 in Algorithm D. which requires [Vabb] [V] iterations. This part can also be separated from the outer loop, because the yk+1 satisfying the condition in the line 13 is uniquely determined the first sub-token of [d++1]y->ess> Thus the nested loop can be deformed into single loop over I++1 E V. Moreover, we observe that the token Te-1 with low probability can be ignored as it will not contribute to the final summation. Therefore we can restrict the single loop over V to the one over D(k) the top-K tokens with high probabilities. Based on these observations, we can deform the lines 12-15 15 in Algorithm into the lines 12-16 in Algorithm 2 which only requires K iterations. Here K is an arbitrary hyperparameter and we will set it to be a small number K 300 in our experiments. For ablation study with varying K, see Appendix D.7
APPLICATION: ENSEMBLE VIA MAXIMAL COMMON VOCABULARY
Suppose that we have N language models
each defined over its own vocabulary
V. We assume that each p. satisfies the validity condition (7) with respect to a given tokenizer
T (V. [-y, -lA). For simplicity, we further assume that each tokenizer is given by Byte-Pair
Encoding (BPE; Gage 1994); SSenniich et al. (0166) with a set of token pairs M, C V/? Recall that, in BPE tokenization, a given text dj On A is first viewed sequence of byte tokens T1 ....... Lt E V,", and then iteratively each adjacent tokens 2yT++1 satisfying (It, Z1+1) E .,, are merged, i.e., replaced by the new token 2/ == 21 E V.
To ensemble language models with different vocabularies, we introduce the maximal common vocabulary Vn and an associated tokenizer Tn- (Vn, 1-lv..-llaaa nested tokenizer for lossless vocabulary reduction described the previous section. Although there is some arbitrariness in the construction of such an associated tokenizer, we consider BPE tokenizer constructed from the first tokenizer Ti, with the vocabulary Vn and token pairs Mn given by:
that it can be used in the
N
Mn = {(11,13) E M1 Vi32 E VnJ. Vn :- 1I=-4 V. i-1
(25)
Then the encoder [-]v,, for Tn is defined by the iterative merging process of BPF, as explained above, with the token pairs Mn. Although here we focused on a specific construction based on the BPE algorithm, the construction of To is not limited to BPE; other deterministic tokenizations such as the Unigram tokenization (Kudo 2018) can also be employed with appropriate modifications.
Let PV: denote the vocabulary reduced model of Pv; with the nested tokenizer Ty-v, with respect to T-, i..., [=vly, := [[=a]a],, for each token 2; E V, Each Pv,-V, is an independent language model over the common vocabulary Vn but exactly shares the quality of generated texts with the original model pv; by Theorem 3.1 Then we can define the ensemble of the given N language models (pv, )==1, NN that of the vocabulary reduced models (pv, -V Ji=1,
Pens (1 virr x II IV. (we41 I/r)), where yı, ",941 Vn-
(26)
IIn this paper, we mainly consider the ensemble by products of experts Hinton 1999., which is also known logit-level ensemble for neural networks. See Appendix D for more detailed discussion.
8

---

Published as a conference paper at ICLR 2026
Input
Question: Janet's a ducks lay 16 eggo per day, She eats theee for breakfast every nocning and bakes nutrine for her friends every day vith tours She cells the remalnder at the Tarnere" warket daily for 92 per fresh duck egg. Fow mach in dol lane does she make every day at the farierss market PynAngvers
Original
Janet sellls
- <4166354-00 eggs per MayaAnShe maked 82
cC7-91185188 dollars per oog.nnetE
Bytes
Janct 361:5 31- -0416-3-4 9989 c009 pop A8g.nnne praecl 65at B80
nakes
5-299
Bo518 3or per deyanneti
2-yyu
wage day
per Bay.
Bytes
189918
S-Byte
Janee 2MI23
pe: Anshl
Talua 82
082298189918 dollars per day.
Figure 3: example of text generation by greedy decoding of original model (Llama3.2-30) and vocabulary-reducee models with varying maximal token lengths from 1 to 8 bytes. Each token is colored periodically for visibility. See Appendix D.4 for other examples.
Compared to the previous work of the byte-level ensemble (Phan al. 2025 Vieira et al. 2025), approach with the maximal common vocabulary enables faster generation because it can generate multiple bytes by single inference of the ensemble model, with almost the same inference cost of each vocabulary reduced model as the corresponding byte-level model.
5 EXPERIMENTS
In this section, we conduct experiments to validate (i) whether our proposed method can reduce given vocabularies to various uub-vocabularies without loss in accuracy and (ii) whether our proposed method can be effectively applied to token-level ensemble. See Appendix C for experimental details.
5.1 EXPERIMENTS ON VOCABULARY REDUCTION
Given a language model with vocabulary V, we consider the N-bytes sub-vocabulary V&N {u E V [e]((u]a) < N and assess the capability of vocabulary reduction from V to VeN with = 1,2, 4,8. 8. As a baseline for vocabulary reduction, we consider Naive Restriction that simply puts zeros to the probabilities of excluded tokens V VeN and renormalizes the remaining probabilities over VeN- In T we evaluated the accuracy of vocabulary-reducedd models by the above baseline (Naive) and our algorithm (K-LVR) on the benchmark GSM8K. The results show that our algorithm (K -LVR) overall achieves almost same accuracy as the original model over the full vocabulary. In Figure sub-vocabularies VEN. and observe the consistent results except for the 1-byte case. In the 1-byte case, the generated text deviates from the original one after the first sentence due the nature of greedy decoding but the final answer is still consistent with the original one as Theorem 3.1 implied.
show example of greedy decoding for K-LVR models with the
5.2 EXPERIMENTS ON ENSEMBLE VIA MAXIMAL COMMON VOCABULARY (MCV)
In Table as an application of the vocabulary reduction, we conducted experiments with ensemble of two language models of similar accuracy: Qwen2.5-3B and Falcon3-7B. The former model has 151,665 tokens and the latter has 131,072 tokens, whose maximal common vocabulary consists of 63,552 tokens. Union and Naive (MCV) refer the heuristic baselines described in Appendix C.2 From the results, we can see that (i) ensemble with K-LVR over MCV overall achieves comparable accuracy to the byte-level ensemble (Phan al. 2025) and other baselines, and (ii) the heuristic baselines catastrophically fail in some cases, while our K-LVR consistently works well even in such cases. Moreover, as shown in Table 3 in Appendix, we observed that the ensemble over MCV is actually faster than the byte-level ensemble as expected at first, which highlights the benefit of generalization to arbitrary sub-vocabularies beyond one-bytes.
6 RELATED WORK
Vocabulary reduction. There has been a line of research on vocabulary reduction, specifically aiming for compressing the size of language models. for e.g., Ataman al. (2017); Gee al.
Heree we define len(a1 .N) = N for aj .. -N E A' "See Appendix B for detailed discussion the inconsistency accured greedy decoding.

---

Published as a conference paper at ICLR 2026
Mexiels
Methods
RRyles
S: Rytes
S Bytes
S Bytes
Siugle
GSM8K
MATH
ACP
MMLU Pro
OLMo2-18
X-IVR
Naive
30.40
30,40
0.00
31,46
0.00
31.39
7.28
31.77
30.55
Falcon3-7B
Qwen2.5.3B
76.65
71.27
27.86
26.14
36.29
36.71
37.71
42.71
1-33
Natce K-LVR
26.00
26.31
0.00
26.23
0.00
25.93
11:52
26.16
26.31
Ensemble (PoR)
Qw3n2.5-3B
Nake: K-LVR
71.27
71,19
8.00
70,43
0.00
23.65
71.42
72.18
65.96
Nuive (MCV)
Union Yao et 2002
24.94
27.60
21.71
19.57
25.86
25.71
2.07
1.93
Falcon3-7B
X-IVR
Naive
76.05
0,00
0.00
34.72
79.23
72.40
K-LVR (1-Bytes)
K-LVR (MCV)
82.49
81.12
30.71
30.29
35.43
34.71
42,00
41.21
Table 1: Results of vocabulary reduction GSM8K,
Table 2: Results of ensemble by product of experts
with varying maximal token lengths from to 8 bytes. Full refers to the original models, Naive the baseline of naive restriction and K-LVR is our algorithm.
(PoE: Hinton (1999). Union refers the baseline of the union vocabulary and Naive (MCV) refers the baseline of naive restriction to the MCV. (Ap-
pendix C.2
(2022) y Ushio et al. (2023): : Bogoychev et al. (2024):
Chizhov et al. (2024) x Nozaki et al. (2025), )
while their motivation differs from ours. Some of them proposed methods like naive restriction with
2024), and others proposed modify embedding vectors with additional training to keep accuracy. Recently, apart from this line of research, several work (Phan et al. 2025 Vieira et al. 2025 Hayase et al. 2025) have proposed methods to convert token-level language models into the equivalent byte-level language models in inference-time [Phan et al. (2025) derived the first efficient method for the byte-level reduction under the validity assumption, and empirically confirmed its applicability to ensemble with different vocabularies. |Vieira et al.] (2025) derived the byte-level reduction under general condition, while it requires more computation for accurate conversion. Our framework can seen as generalization of Phan et al. (2025) from bytes arbitrary sub-vocabularies under the validity assumption.
heuristics of vocabulary selection (Ushio et al. 2023 Bogoychev et al..
Ensemble with different vocabularies. Specifically for ensemble of language models with different vocabularies, previous work have taken several heuristic approaches based on (i) partial matching between tokens as strings (Jiang et al.) 2023 Wan et al. 20244 Liu et al. 2025), (ii) similarity between tokens in the shared embedding space (Xu et al. [022 Huang et al. 2024). and (iii) the union vocabulary YYu et al. 2024 Yao et al. 2025). Although the first and second approaches seem to work well in experiments, they have no theoretical guarantee for their success and it is also difficult for them to be applied beyond ensemble. The second approach also requires models to share the same embedding space. The third approach, which simply extends next-token distributions by putting zero tokens, has been reported to beat the previous heuristic methods despite of its simplicity (Yao et al.) (2025). However, by its nature, it possibly struggles capture the mutual relations between out-of- out-of- vocabulary tokens since it completely ignores any partial match as strings, which may lead to the perfomance drop observed in our experiments.
probabilityies to out-of-vocabulat
CONCLUSION
In this paper, we established the first theoretical framework of lossless vocabulary reduction, which reduces given next-token distribution to the one with an arbitrary sub-vocabulary while preserving the generation quality. Compared to the previous byte-level reduction, our framework enables more flexible and efficient cooperation between different language models through their common vocabularies. We hope that our work will open up new research direction for efficient lossless cooperation between language models with different vocabularies in a principled way.
REPRODUCIBILITY STATEMENT
The experimental details are provided in Appendix C All proofs are provided in Sections 3 and A
REFERENCES
Duygu Ataman, Matteo Negri, Marco Turchi, and Marcello Federico. Linguistically motivated vocabulary reduction for neural machine translation from turkish to english. The Prague Bulletin of Mathematical Linguistics, 108(1):331-343 2017.
10

---

Published as a conference paper at ICLR 2026
Nikolay Bogoychev, Pinzhen Chen, Barry Haddow, and Alexandra Birch. The ups and downs of large language model inference with vocabulary trimming by language heuristics. In Shabnam Tafreshi, Arjun Akula, João Sedoc, Aleksandr Drozd, Anna Rogers, and Anna Rumshisky (eds.), Proceedings of the Fifth Workshop on Insights from Negative Results in NLP. pp. 148-153, Mexico City, Mexico, June 2024. Association for Computational Linguistics. doi: 10. 10.18653/v1/202 insights- 1.17. URL https: /ttts::/aclantho//// awt.aaaaaanntoooooocaaaa wwt.//00.0//2253/ insiinssiist.. 1.177
Ond rej Bojar, Rajen Chatterjee, Christian Federmann, Yvette Graham, Barry Haddow, Matthias Huck, Antonio Jimeno Yepes, Philipp Koehn, Varvara Logacheva, Christof Monz, Matteo Negri, Aurelie Neveol, Mariana Neves, Martin Popel, Matt Post, Raphael Rubino, Carolina Scarton, Lucia Specia, Marco Turchi, Karin Verspoor, and Marcos Zampieri. Findings the 2016 conference machine translation. In Proceedings of the First Conference Machine Translation, pp. 131-198, Berlin, Germany, August 2016. Association for Computational Linguistics. URL
http:/ www. , ac web. org/ antho ogy/t/////ooo/o / W1 6/W16 6 2301
Ondrej Bojar, Christian Buck, Christian Federmann, Barry Haddow, Philipp Koehn, Johannes Leveling, Christof Monz, Pavel Pecina, Matt Post, Herve Saint-Amand, Radu Soricut, Lucia Specia, and Ale s Tamchyna. Findings of the 2014 workshop on statistical machine translation. In Proceedings of the Ninth Workshop Statistical Machine Translation, pp. 12-58, Baltimore, Maryland, USA, June 2014. Association for Computational Linguistics. URL http: http:://ww aclweb. wwg. antha / W14 0101---3322
Pavel Chizhov, Catherine Arnett, Elizaveta Korotkova, and Ivan Yamshchikov. BPE gets picky: Efficient vocabulary refinement during tokenizer training. In Yaser Al-Onaizan, Mo- hit Bansal, and Yun-Nung Chen (eds.), Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pp. 16587-16604, Miami, Florida, USA, November 2024. URL
Association for Computational Linguisties. doi: 10.
https://ace aatannooooog .rg. 2024. emn camnlpp p-ma i n. 9257
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 arXiv:21 10. 14168, 2021.
Team Fal The falcon family of open models, December 2024. URL https://
huggingface co/b wo///oo//aal///o/ooooo/o/oooa/aa fcon33
Philip Gage. A new algorithm for data compression. C Users J., 12(2):23-38, February 1994. ISSN 0898-9788.
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, Eric Tang, Anish Thite, Ben Wang, Kevin Wang, and Andy Zou. The language model evaluation www./zzooo..coooooo http://eno...rgrreeeee/ http://eeoooorooeeeeeeee
harness, 07 2024. httht::: http:::://eenoooooom
Leonidas Gee, Andrea Zugarini, Leonardo Rigutini, and Paolo Torroni. Fast vocabulary transfer for language model compression. In Yunyao Li and Angeliki Lazaridou (eds.), Proceedings of the 2022 Conference on Empirical Methods Natural Language Processing: Industry Track, pp. 409-416, Abu Dhabi, UAE, December 2022. Association for Computational Linguistics. doi: 10.18633/v1/ 2022. 1nt.emmmlpinndutry..111 URL httpt::t////t........t http:::://acllaathloggooo http://rrgg2222...mmmmmmoootttt.
417
Jonathan Hayase, Alisa Liu, Noah A Smith, and Sewoong Oh. Sampling from your language model one byte at a time. arXiv preprint arXiv:2506. /4/23, 2025.
Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. Measuring massive multitask language understanding. In International Confer- ence on Learning Representations, 2021a. https:/:: httttps://opereeee /wwp//eeeeeeeeeeeeee ew net. / forum? i
d7KB 3GmQ
Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the MATH dataset. In
11

---

Published as a conference paper at ICLR 2026
Thirty-fifth Conference Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021b.
Geoffrey Hinton. Products of experts. Proceedings of the Ninth International Conference on Artificial Neural Networks, 1999.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network. arXiv preprint arXiv:1503.0253/1 2015.
Yichong Huang, Xiaocheng Feng, Baohang Li, Yang Xiang, Hui Wang, Ting Liu, and Bing Qin. Ensemble learning for heterogeneous large language models with deep parallel collaboration. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL net meet/forummii07/rAAAAD0
pettps://openreeee
Mojan Javaheripi, Sébastien Bubeck, Marah Abdin, Jyoti Aneja, Sebastien Bubeck, Caio César Teodoro Mendes, Weizhu Chen, Allie Del Giorno, Ronen Eldan, Sivakanth Gopi, et al. Phi-2: The surprising power of small language models. Microsoft Re-
search Blog, 2023. URL htttps:/www.... crosoft.
Dongfu Jiang, Xiang Ren, and Bill Yuchen Lin. LLM-blender: Ensembling large language mod- els with pairwise ranking and generative fusion. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.), Proceedings of the ó Anmual Meeting of the Association for Com- putational Linguistics (Volume 1: Long Papers), pp. 14165-14178, Toronto, Canada, July 2023. Association for Computational Linguistics. doi: 10. 20.18653/11/0233 hwtp:/oo.....-oooo.999...... URL attps://acLanthooogg wwwpaaawwwwooooooo/..o..a.. wwtp acl-oono....oonnn-.oo. 7927
Michael I Jordan and Robert A Jacobs. Hierarchical mixtures of experts and the em algorithm. Neural computation, 181-244,,, 1994.
Harsha Kokel, Michael Katz, Kavitha Srinivas, and Shirin Sohrabi. Acpbench: Reasoning about action, change, and planning. Proceedings of the AAAI Conference on Artificial Intelligence, 39(25): 06559-265666 Apr. 2025. URL URLhttts::///// aaai org/index. hwtp:pppppp.Aaaaaeeaaaa Aww.A/Aaatiitiaa.a view/34857
Taku Kudo. Subword regularization: Improving neural network translation models with multiple subword candidates. In Iryna Gurevych and Yusuke Miyao (eds.). Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 66-75, Melbourne, Australia, July 2018. Association for Computational Linguistics. doi: 10. 10.18653/v1/P18- 1007. UtI.htttss://ack antho www.aaanttt.o...oooooooo.o.o.. 1007/
Taku Kudo and John Richardson. SentencePiece: A simple and language independent subword tokenizer and detokenizer for neural text processing. In Eduardo Blanco and Wei Lu (eds.), Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pp. 66-71, Brussels, Belgium, November 2018. Association for Com- putational Linguistics. doi: 10.18653/v 10D////11/11820111111 2012. URL http:::ss//acaaatooooooo org
D18-2012/
Yaniv Leviathan, Matan Kalman, and Yossi Matias. Fast inference from transformers via speculative decoding. In Andreas Krause, Emma Brunskill. Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 19286. PMLR, 23- 29 Jul 2023. URL htt.:ttttpp::/prceellli. wtw.:sssss.rrppr.s..mmmmmmm www.:.pressss.... wttpessss/222//eeaaaaaaaaa
html
Aitor Lewkowycz, Anders Johan Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski, Vinay Venkatesh Ramasesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Gutman-Solo, Yuhuai Wu, Behnam Neyshabur, Guy Gur-Ari, and Vedant Misra. Solving quantitative rea- soning problems with language models. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL httts::/ net ottp
12

---

Published as a conference paper at ICLR 2026
Cong Liu, Xiaojun Quan, Yan Pan, Weigang Wu, Xu Chen, and Liang Lin. Cool-fusion: Fuse large language models without training. In Wanxiang Che, Joyce Nabende, Ekaterina Shutova, and Mohammad Taher Pilchvar (eds.), Proceedings of the 63rd Anmual Meeting of the Association for Computational Linguistics ( (Volume I: Long Papers), pp. 10617-10627, Vienna, Austria, July 2025. Association for Computational Linguistics. ISBN 979-8-999----17 doi: 10. 10.18633/v1/ 3025.acl-long.555 //I//ttpss//acalaatooooooooog.o
Meta. Introducing llaaa 3.1: Our most capable models to date, 2024a. URL https://ai.nnt meta
com/blog blog/met..eeo 11am--311
Meta.
Llama 3.2: Revolutionizing edge ai
and vision with open, cus-
tomizable models, 2024b.
URL https://at http:////aa.amaaa...ae wwt.amtttaoobbba.mmmmmmmmm htom/bllo /
T1ama- - (012-cconnct-2220 soomeett-222-viiinn-neee
mobi le devices/
Eric Mitchell, Rafael Rafailov, Archit Sharma, Chelsea Finn, and Christopher D Manning. An
emulator for fine-tuning large language models using small language models. The Twelfth International Conference on Learning Representations, 2024. URL
Yuta Nozaki, Dai Nakashima, Ryo Sato, Naoki Asaba, and Shintaro Kawamura. Efficient vocabulary reduction for small language models. In Owen Rambow, Leo Wanner, Marianna Apidianaki, Hend Al-Khalifa Barbara Di Eugenio. Steven Schockaert, Kareem Darwish, and Apoorv Agarwal (cds.), Proceedings of the 3/st International Conference on Computational Linguistics: Industry Track, pp. 771-783, Abu Dhabi, UAE, January 2025. Association for Computational Linguisties. URL wrg.//2.g.202222 wtwpelloyy.oogg////// 2025. caw.ssoooonnnnnnineeeeee wnw.innuuuurr....m
Team OLMo, Pete Walsh, Luca Soldaini, Dirk Groeneveld, Kyle Lo, Shane Arora, Akshita Bhagia, Yuling Gu, Shengyi Huang, Matt Jordan, Nathan Lambert, Dustin Schwenk, Oyvind Tafjord, Taira Anderson, David Atkinson, Faeze Brahman, Christopher Clark, Pradeep Dasigi. Nouha Dziri, Michal Guerquin, Hamish Ivison, Pang Wei Koh, Jiacheng Liu, Saumya Malik, William Merrill, Lester James V. Miranda, Jacob Morrison, Tyler Murray, Crystal Nam. Valentina Pyatkin, Aman Rangapur, Michael Schmitz, Sam Skjonsberg, David Wadden, Christopher Wilhelm, Michael Wilson, Luke Zettlemoyer, Ali Farhadi, Noah A. Smith, and Hannaneh Hajishirzi. 2 olmo 2 furious, 2024. TtRl:ttts:///// /arxiiiivii org abs 2501 00656
Buu Phan, Marton Havasi, Matthew J. Muckley, and Karen Ullrich. Understanding and mitigating tokenization bias in language models. In ICML 2024 Workshop Theoretical Foundations of Foundation Models, 2024. URL
net fttp://fooomidddee doo
Buu Phan, Brandon Amos, Itai Gat, Marton Havasi, Matthew J. Muckley, and Karen Ullrich. Exact byte-level probabilities from tokenized language models for FIM-task: and model ensembles. In The Thirteenth International Conference on Learning Representations, 2025. URL https
//openrevi ew net. wtt.//oormrdccoeoo Fo
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. 2019.
Mike Schuster and Kaisuke Nakajima. Japanese and korean voice search. In 2012 JEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5149-5152, 2012. doi: 10. 2A.1009CASSPP.2222.2253
Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural machine translation of rare words with subword units. In Katrin Erk and Noah A. Smith (eds.), Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp. 1715-1725, Berlin, Germany, August 2016. Association for Computational Linguistics. doi: 10. 18553/ URL htt.:htss//aaaaatooott/
1162/
Asahi Ushio, Yi Zhou, and Jose Camacho-Collados. Efficient multilingual language model compres- sion through vocabulary trimming. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Findings of the Association for Computational Linguistics: EMNLP 2023, pp. 14725-14777 14739, Singapore, De- cember 2023. Association for Computational Linguistics. doi: 10. 18..1813/v11/// 1 http:///1/22222mmmm// ndi 981. h https::/p/.............t /cal antho wog.oooo..rrg/22333 fid ngs- emn
981/
13

---

Published as a conference paper at ICLR 2026
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 characters. In second International Conference on Machine Learning, 2025. URL htttps://ppenreee ew net forum? o=tt://ooummmmssssroootrt
Fanqi Wan, Xinting Huang, Deng Cai, Xiaojun Quan, Wei Bi, and Shuming Shi. Knowledge fusion of large language models. In The Twelfth International Conference on Learning Representations,
2024. URL https:: http://ppppeeeeeeeee ott.pps///eeeeee........t. For 1ttp://ww....trrraaoaa--011-11--
Yubo Wang, Xueguang Ma, Ge Zhang, Yuansheng Ni, Abhranil Chandra, Shiguang Guo, Weiming Ren, Aaran Arulraj, Xuan He, Ziyan Jiang, Tianle Li, Max Ku, Kai Wang, Alex Zhuang, Rongqi Fan, Xiang Yue, and Wenhu Chen. MMLU-pro: A more robust and challenging multi-task language understanding benchmark. In The Thirty-eight Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2024. httph:tt/:////mm /openrevi wwt.
/
Yangyifan Xu, Jinliang Lu, and Jiajun Zhang, Bridging the gap between different vocabularies for LLM ensemble. In Kevin Duh, Helena Gomez, and Steven Bethard (eds.), Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies (
(Volume 1: Long Papers). pp. 7140-7152 Mexico City, Mexico, June 2024. Association for Computational Linguistics. doi: 10.
URL
htwphhhooooooorgg////. org/ www.caaacc-aaaaa 1on..onn...9.
An Yang, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang, Haoran Wei, et al. Qwen2. 5 technical report. arXiv preprint 151 2024.
Yuxuan Yao. Han Wu, Mingyang LIU, Sichun Luo, Xiongwei Han, Jie Liu, Zhijiang Guo, and Necessity of top-k union for large language model ensembling. In The Thirteenth International Conference on Learning Representations, 2025. URL
Linqi Song.
htttps://ppenreiiie net/ Ftto/oormmmm-
François Yergeau. Utf-8, transformation format of iso 10646. Technical report, 2003. URL
iet watg///c/httm//eaeett/ee
Alex Young, Bei Chen, Chao Li, Chengen Huang, Ge Zhang, Guanwei Zhang, Guoyin Wang, Heng Li, Jiangcheng Zhu, Jianqun Chen, et al. Yi: Open foundation models by 01. ai. arXiv preprint 24X1::2403.0462, 2024.
Yao-Ching Yu, Chun Chih Kuo, Ye Ziqi, Chang Yucheng, and Yueh-Se Li. Breaking the ceiling of the LLM community by treating token generation as classification for ensembling. In Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen (eds.), Findings of the Association for Computational Linguistics: EMNLP 2024, pp. 1826-1839, Miami, Florida, USA, November 2024. Association for Computational Linguistics. doi: 10.18653/w1/2224 findings-cmmllp URL httpes://eelanntoooooooooo///222 wiw.nnisiiiiiiinnninnnnnn 99/
14

---

Published as a conference paper at ICLR 2026
A PROOFS FOR SECTION
Lemma A.1. Let and PV- be as in Lemma 3.2
For any tokens Vi:k E V we have
PV-+Venn (V1:44)=
Pv(
(27)
En (wra)
Proof. Here we introduce the following notation:
c V. (Ui:k) =
Cy. (U1:k) V*,
(28)
Then we have the following decomposition for the relative covering set:
Cv. (B1:k) = L
V.Va (y1:k)
tEN
Using these notation, we have
Py-Vaus (V1:**)
Σ
PV-Veun (V1:K)
91K EVi
Σ
Σ
Pv(E1r)
Ethiks
FIVEV'
Σ
pv(xI:)
[FLTIV- Veub Etna
Σ
Pv(x1r)
FLV [ailv Van (erlVV-Von Eviik
Σ
pv(TIT)
KEN
FLTEV"
[an ln " (Rily-- Evrits v "[x, 1]v --v--au Vout Edrsk
E
Σ PLEVV
Σ
pv(FiT)
Ret1o EV-
[mi]y Vaub "[Zilv Vout Evia. [m] v Van "Ix Ilv- Evrin
(v(1
IEN an V.Man (wir)
Σ
(y(x
#1: CGV. (21a)
Lemma A.2. Under the notation Section
Fnst E Cv. (Mix) if and only if wi satisfies either
(i) Fia E Cv.vas (y1.k-1) and yi:k < [21:1v++Van
or (ii) Fia is valid and satisfies [x1---]y--- DiRk-1 and 3/k - [xr]vmn.
Proof. First of all, we note that Fi.k [ litee-ll--un.. for some k' < k by the assumption Iia Cv.van (y1:)). Then the last token V, can be expanded as [zzly=vem. = #1 ... E 4 In the case of k' k 1, it follows that ys x [2 and thus corresponds the case (ii). On the other hand, [21==-1] -Yva. 91.k" y1.k-1 1*, which corresponds to the case (i).
lc 1, we have Ti. E Cy, (81 because [z1: E Vick- and
15

---

Published as a conference paper at ICLR 2026
B AN EXAMPLE OF LOSSLESS VOCABULARY REDUCTION
Here we assume that A {0, } instead of a set of bytes. Let := {(0), (1), {00), (001)} and Vaub {(0), (1), (00) where each (-) denotes token. We suppose that the corresponding tokenizations are given by the greedy forward-matching tokenization, which maps each input bits b1- b,...bw ...b. E {0, 10, the longest matching tokens in the vocabulary, V Vuu., from left to right.
Then we consider a language model py over V/ given by:
0.1 if ro (0),
0.6 1 (0),
0.1 if xo (I);
I1 (1),
py(2)*)= =
Pv( zo (00)) =
(29)
0.5 if (00),
0.3 if = (00),
0.3 if 3D (001),
0.1 if (001),
Note that the tokens (1) ) are invalid since 001 is tokenized as (001) in the greedy forward- matching tokenization, and thus the probability pv(œ1 = (1) | xо = (00)) is set to
To compute pV- (vo), we first calculate the relative covers:
C.v ((0) (0)), Cv.Vau ((1) {(1)) Cr. ((00)) {(00), (001)),
(30)
Then we can compute the marginal probabilities pv- (y0*) as
0.1 (= p)((0))))
if yo (0),
PV-Vens (30+) = 0.1 (= pr((1)*)
if you = (1).
(31)
0.8 (= (=
-
if (00),
Now suppose that ye = (00) is sampled. To derive the next-token probability PV-Veet (v1 yo = (00)). we need to consider the following relative covers:
Vy.yaus ((00) (0)) = { ((00) (0)), Cy. ((00) (1)) = {001)))
Cv. (00)) (00)) = {(00) (00), (00) (001))
Then the marginal probabilities PV-VVeu ((00) +) is obtained as follows:
0.3 (v00 (0)+))
if yı (0),
PV-VVam ((00)
0.3 (= (v00 )))
if yı (1),
(32)
0.2 (= (00) (00)*) + pv (00) (001)+))
yı (00),
Finally, we obtain the next-token distribution by normalizing the above marginal probabilities:
0.375
if y = (0),
PV-VVen (31 1 yo (00))
0.375
if y (1);
(33)
0.25 if y1 (00),
Now we compare the corresponding text distributions for pv and pV-Vass- Especially, we cal- culate the probability that the output text starts with "000". For the case of py, such a prob- ability is nothing but the probability of xo = (00). which is 0.5, since the text "000...* (00){(00)).. ..., by the greedy forward-
be tokenized either (0)) ... (00) matching tokenization. On the other hand, for the case of py-V the text "000... can be tokenized as either (00) or (00) (00) and thus the corresponding probability is given by PV-VVeu ((00) (0)*) )) + PV-VV... ((0)) (00)*) 0.3 + 0.2 = 0.5. Therefore, the two distributions and Pv-VV... are equally plausible output the text starting with "000".
Also, here we can observe the following fact: even if two liken-distributions are equivalent at the
level of their byte-level distributions, the texts obtained by greedy decoding may be different from each other in general. Indeed, on the one hand, the greedy decoding for the original distribution pv
generates the first token 2i = (00) and the second token 21 = (0) according to equation (29.. On
the other hand, the greedy decoding for the reduced distribution Py-+Vau. may generate yo (00)
and y1 = (1) according to equation (31) and (32), resulting in a different text 001 from the former
one 000, even though both distributions have the same text distribution by Theorem 3.1
This behavior is dependent the implementation of greedy decoding siene there are two tokens (y1 (0)
and y1 (0)) achieving the maximal conditional prohahility.
16

---

Published as a conference paper at ICLR 2026
C EXPERIMENTAL DETAILS
C.1
SETUPS
Models.
Qwen 2.5 Yang et al. 2024): A family of large language models developed by Qwen Team, ranging from 0.5B to 72B parameters. The tokenizer is implemented by the byte-level BPE with the vocabulary consisting of 151,665 tokens.
OLMo 2 {OLMo et al. 2024): A family of large language models developed by Allen Institute for AI, ranging from 1B to 32B parameters. The tokenizer is implemented by the byte-level BPE with the vocabulary consisting of 100,278 tokens.
Llama 3.1 and 3.2 (Meta 2024a b A family of large language models developed by Meta AI, ranging from 1B to 908 parameters. The tokenizer is implemented by the byte-level BPE with the vocabulary consisting of 128,256 tokens.
Falcon (Falcon- 2024): A family of large language models developed by Technology
Innovation Institute (TII), ranging from IB to 10B parameters. The tokenizer is implemented by the byte-level BPE with the vocabulary consisting of 131,072 tokens.
Phi (Javaheripi et al. 2023): A large language model with 3B parameters, developed by Microsoft. The tokenizer is implemented by the byte-level BPE with the vocabulary consisting of 50,295 tokens.
Yi 1.5 Young et al. 2024): A family of large language models developed by 01.AI, ranging from 6B to 34B parameters. The tokenizer is implemented by the byte-level BPE with the vocabulary consisting of 63,992 tokens.
Datasets. We used the following datasets for evaluating language models through the Im-evaluation- harness library (Gao et al. 2024) with default options.
GSM8K (obbe et al. 2021): y dataset consisting of grade-school math questions. Each question has an example of chain-of- of-thhught argument followed by an open-ended answer. For each question, 5 pairs of a question and its answer are provided for language models by default. We reported the percentage of strictly-extracted correct answers.
MATH (Hendrycks et al., 2021bb: A dataset of mathematical problem soaemn--oovinngg tasks in 7 categories that require numerical and logical reasoning skills. Each question has an example of chain-of-thought argument followed by open-ended answer. For each question, pairs of question and its answer are provided for language models, following the setting by Lewkowycz et al. (2022). We reported the percentage of correct answers after which processed symbolically. with randomly sampled 100 questions from each category.
ACPBench (Kokel et al. 2025): A dataset of tasks in 7 categories, evaluating the reasoning ability about action, change, and planning, with multiple answer choices. Each question has an example of chain-of of-thought argument followed by the correct answer. For each question, pairs a question and its answer are provided for language models by default. We reported the percentage of correct answers for the questions with multiple choices, with randomly sampled 100 questions from each category.
MMLU-Pro (Wang et al., 2024): A dataset of question-ansee -nwwerrnn tasks in 14 categories, enhancing MMLU (Hendrycks et al. (021a) by more challenging questions that require reasoning skills with multiple answer choices. Each question has an example of chain-of- thought argument followed by the correct answer. For each question, 5 pairs of a question and its answer are provided for language models by default. We reported the percentage of correct answers, with randomly sampled 100 questions from each category.
Decoding method. Unless otherwise stated, we employed the greedy decoding for sampling tokens, ie., iteratively sampling tokens with the highest probability, for both simpliticty and reproducibility. is noteworthy that, even if two token distributions have the same text distribution, the resulting texts by greedy decoding for these models may be different from each other, as discussed in Appendix B
17

---

Published as a conference paper at ICLR 2026
C.2 BASELINES
Baselines for vocabulary reduction.
Naive restriction is the most straightforward method for vocabulary reduction, but with theoretical guarantee for accuracy. Let p (x1)..-))) be next-token distribution over V. and let Veub be a subset of V. The naive restriction PVaa (34+41331 ys) is defined we first retokenize it in V by I1 .. == [[y ... y.laly Then we compute the next- token distribution ( [m] ..,)),, forcibly replace Py(*+41 ...2)) by for all D++1 E sub. and renormalize it. Finally, we sample a next token yk+1 = 2++1 E Vsub from the renormalized distribution.
Naive Restriction:
follows: Given previously sampled tokens y1 .. ye+
Byte-Level Reduction (Phan et al. 2025 Since our lossless vocabulary reduction (LVR) can be seen as a generalization the byte-level reduction proposed in Phaa et al. (0025) LVR with 1-byte tokens is actually equivalent to the byte-level reduction.
Baselines for ensemble with different vocabularies.
Ensemble over Union Vocabulary (Yu et al., 2024 Yao et al., 2025): Given language models pv; with different vocabularies V,, can simply extend each next-token distribution Pv, (x1+1 ... ... xτ) to the one over the union vocabulary Vu == U, by putting zero probabilities for #++1 Vu V4- More specifically, to extend next-token distributions of the i-th model, given previous samples ... E Vū, we first take the retokenization 31 .. Zt
[[y] ... -ykklyy and then compute the next-token distribution of the i-th model, following the procedure in Yao et al. (2025).
Ensemble with Naive Restriction over MCV: We just apply the naive restriction with Vaub == Vn (as defined in Section to each language model, and then compute their ensemble distribution.
18

---

Published as a conference paper at ICLR 2026
D ADDITIONAL EXPERIMENTAL RESULTS
D.1 INFERENCE EFFICIENCY
OLMo2-1B & Qwen2.5-0.5B
Qwen2.5-3B & Falcon3-7B
Ensemble (1-Byte)
25.72 + 1.78 (bytes/sec)
17.03 + 0.70 (bytes/sec)
Ensemble (MCV)
46.78 + 9.29 (byles/sec)
33.50 + 5.41 (bytes/sec)
Table 3: Inference speed over 100 questions on GSM8K. Since the average bytes of tokens in maximal common vocabulary (MCV) is obviously greater than byte, the ensemble over MCV can generate more bytes per second than the byte-level ensemble (Phan et al. 2025).
D.2 EXTENDED RESULTS ON VOCABULARY REDUCTION
Methods
Full
Bytes
Bytes
S Byles
Dytes
Qwen2.5-0.5B
Naive
34.27
0.00
0.00
6.90
30.86
Naive K-LVR
0.00
0.00
7.28
30.55
OLMo2-1B
30.40
31.46
31.39
31.77
Llama3.22 3-3BBB
Naive K-LVR
26.00
0.00
0.00
11.52
26.31
26.31
26.23
25.93
26.16
Qwea2.5-3B
Naive K -LLVR
71.27
0.00
0.00
23.65
65.96
71.19
70.43
71.42
72.18
Falcon37B
Naive
76.65
0.00
0.00
34.72
72.40
K LVR
78.92
79.38
79.30
79.23
Table 4: Quantitative evaluations of vocabulary reduction on GSM8K, with varying maximal token lengths from 1 to & bytes. Full refers the original models, Naive is the baseline of naive restriction (Appendix C and K-LVR is our algorithm.
D.3 PRODUCTS EXPERTS AND MIXTURES OF EXPERTS
There are two straightforward definitions for ensemble of probability distributions p1 (1(r),.. .. , (x) over the same domain X:
Products of Experts (PoE; Hinton (999)) with uniform weights:
Pens (I) x Pi(x)
Mixtures of Experts (MoE; Jordan & Jacobs 1994 with uniform weights:
Pens (x) x Σ (c(x)
Intuitively, PoE corresponds the probability of sampling the same simultaneously from all distributions (r),, and MoE corresponds to the probability of sampling r from some randomly- chosen distribution p: (z). As argued in Hinton 1999). the former ensemble more suitable to high-dimensional probabilities, including next-token distributions over the vocabulary of more than hundreds or thousands tokens, than the latter ensemble. Indeed, in the case of next-token distributions, sampled token from the MoE model is preferred by some next-token distribution Pi, (x)) but may be unfavored by the other distributions, which causes the distributional shift the next sampling phase.
In addition to the results in the main paper, performed experiments of both PoE and MoE with small models (Table and larger models (Table(6). Interestingly. while the heuristic baselines (Union and Naive) overall worked well with the MoE ensemble, they catastrophically failed in some cases with the PoE ensemble. On the other hand, our approach of lossless vocabulary reduction works well in both cases, which suggests the broader applicability of our approach than the heuristic ones.
19

---

Published as a conference paper at ICLR 2026
Single
GSM8K
MATH
ACP
MMLU-Pro
Owen2.5-0.50
34,27
13.14
27.71
15.21
OLMo2-1B
33.51
5.86
21.86
13.04
Exsemble (PoE)
Union
2,58
5.00
25.57
15,00
Naive (MCV)
6.37
4.43
25.57
14.93
K-LVR (1-Bytes)
39.12
10.00
25.29
16.64
K-LVR (MCV)
39.27
9.71
26.14
16.21
Ensemble (MoF)
Union
35.03
10.71
25.71
15.57
Naive (MCV)
29,80
10.29
25.71
14.86
K-LVR (1- (1-Bytes)
36.69
9.00
25.86
15.86
K-NR (MCV)
38.13
26.57
Table Results of ensemble by the product of experts (PoE) and the mixture of experts (MoE) with small models.
Single
GSMBK
MATH
ACP
MMLU-PV Pro
Owen2.5-3B
71.27
27.86
36.71
37.71
Falcon3-7B
76.65
26.14
36.29
42.71
Exsemble (PoE)
Union
27.60
19.57
25.86
1.93
Naive (MCV)
21.71
25.71
K-LVR (1-Bytes)
82.49
30.71
35,43
41.21
K-LVR (MCV)
81.12
30.29
34.71
42.00
Ensemble (MoE)
Union
30.86
42.71
Naive (MCV)
75.51
28. 29
25,00
39.14
K-LVR (1 B-tBy)))
81.96
30.43
36.43
42.21
K-IYR (MCV)
81.88
31,57
36.71
42.57
Table 6: Results of ensemble by the product of experts (PoE) and the mixture of experts (MoE) with large models.
D.4 ADDITIONAL EXAMPLES OF VOCABULARY REDUCTION
Injut Queee ious Jush decidex Olipping house. buyx house for $80, and Uhen put.s 050,000
repairs.
increased the
253k.
protis did make7/nnrsser::
1-Dytes
was Incrsased by 1505, sriggnal Ando the
neans was ingressed by 1507100 -e150/11000000 10000/01001.000
$80,
5x88 00 000000000222,00
regai
0000
00-3250,000, Aelbe pesret cest nade $250, 000 580,000 300 R<<250000 000. Amb 120000 AnQwea ionts
00-000000000000000 0-50000
120300x512
2-Ryle
The banle wax Inc waxed By
980, 000, whichh 5kc80000x1 120110010000000111 000. Ando
House
589, 000 C00, xe #480090+5000 00000000000000000000000000000000 1-000133>>-0000 000 ea the heuses Aado has profis is $230, 000 $130, 60g Sx4208 000200000011000 1303000
10 new wortr. 980, 900 $120, 300 $<<80009 12000000 2000039 200, peg. tosho speat
20 poggo 20, 20, 083, Ane4de 2003638 Ingressnng A sa- crauels 120 mi wille 2 hoors
4-Byue
The House was Increased by 150% of g00, g00, which ge<eopon
1040000-15001000 15011000000000000 p00-poos 22, 000, 100000AAA... AnSo Ese house
now wosth 9E0, + 9120, DCg se Deeggoo0Hase 120000 220000>>29,, AnJosh apent 589,000 - 930,
xe80000 D000000011 00000003000000000 3000gxad 30, reugdss-7, Anet* 70030 ingaesttoon:
the Touss, Aado his profig $200, 909 $130,000 9x42009C0 138300
8-Byles
S<X8003E 1100000110000
ircreasec by Ba3,,
house now 51,00,000
130/103 30-150000-1
603. made prosie of $195, $2.2, 000 9c<155030 953009965, 030. Antie? BE000
SrAnpoaes 1om
Table A cherry- example where we found the vocabulary-reduced models (of Falcon3-7B) do not agree with each other in the final answer. Among them, only the 2-bytes and 4- 4-bytes models arrived at the correct answer, though the 2-bytes model made a spelling mistake soon after the answer. The 1 b-yyte model made calculation error in the middle, and the 8-byte model's answer was wrong from the beginning.
20

---

Published as a conference paper at ICLR 2026
D.5
EXTENDED RESULTS OF ENSEMBLE
D.5.1
EVALUATION WITH ADDITIONAL MODEL PAIRS
Single
GSM8K
Single
GSM8K
Single
GSMSK
Single
GSM8K
Qwen2.5-3B
71.27
OLMo2-13B Falcon3-7B
71.87
Phi2-3B
$6.71
Phi2-3B
$6.71
0LMo2-13B
71.87
76.65
Llama3.1 1-18
50.64
Yi1.5-6B
51.86
Fasemble (PoF)
Ensemble (PoF)
Easemble (PoF)
Ensemble (PoF)
K LVR Bytes)
74.00
K LVR Bytes)
72.18
K LVR (1 (yte))
57.62
K-IVR (1 Bytes)
61.56
K-IVR (MCV)
75.13
K-IVR (MCV)
69.37
K-NVR (MCV)
58.53
K-NRR (MCV)
61.64
Table 8: Results of ensemble by product of experts, with various model pairs.
D.5.2 EVALUATION ON TRANSLATION TASKS
Single
En-FFr
Fr->En
En-+D
De->En
Qwen2.5-3B
25.09
35.26
17.23
36.72
Falcon3-7B
33.47
36.05
17.43
33.53
Ensemble (PoE)
K-LVR (1 (1-Bytes)
34.18
35,90
22.21
36.88
K-LVR (MCV)
33.77
36.46
20.46
36.75
Table 9: Results of ensemble by product of experts on translation benchmark. English-Frent Frenchh translation is evaluated the WMT14 dataset (Bojar et al.) (014), and English-German translation evaluated on WMT16 dataset (Bojar et al. 2016). The BLEU scores are reported.
D.5.3
SUMMARY OF COMMON VOCABULARIES
Vocabulary Size
Vocabulary Size
Vocabulary Size
Qwen2.5-3B Falcon3-7B
151,665 131,072
Qwen2.5-3B OLMo2- 13B
151,665 100,278
OLMo2-13B
100,278
Falcon3-7B
131,072
MCV
63,552
MCV
99,162
MCV
62,538
Vocabulary Size
Vocabulary Size
Phi2-3B Yi1.5-6B
50,295
Phi2-3B
50,295
63,992
Llama3.1
128,256
MCV
32,932
MCV
43,247
Table 10: Number of tokens in each vocabulary and the maximal common vocabulary (MCV) used in the ensemble experiments.
D.6 EVALUATION OF VOCABULARY REDUCTION WITH A POSITIVE TEMPERATURE
Models
Methods
Full
Bytes
< 2 Bytes
<
Bytes
S 8 Bytes
Naive
0.00
0.00
0.75
29.19
Phi2-3B
33.66
K-LVR
33.06
33.43
31.99
34.04
Naive K-IVR
0.00
0.00
18.35
43.06
Qwen2.5-3B
45.72
45.72
46.02
45.03
46.63
Naive K-LVR
0.00
0.00
16.68
45.64
Falcon3-7B
47.54
47.61
49.73
50.04
48.60
Table 11:
Results of vocabulary reduction with random sampling with the temperature 1.0. The closeness of accuracy to the Full accuracy implies how well the vocabulary-reduced model approxi- mates the original model as text distributions.
21

---

Published as a conference paper at ICLR 2026
D.7 ABLATION STUDY ON THE CHOICE OF K
D.7.1 EFFECTS ON VOCABULARY REDUCTION
==1
K
10
K = 50
K 250
K 1250
Bytes
79.30
79.08
78.92
79.00
79.15
79.30
Bytes
79.30
79.38
79.45
79.61
79.38
79.38
4 Bytes
78.77
79.08
79.15
79.15
79.15
79.15
Bytes 79.30
79.38
79.23
79.30
79.30
79.30
Original
76.65
Table 12: Accuracy on GSM8K by greedy decoding of Falcon3-7B with various top-K approximation of Algorithm From the results, we can see that even K suffices to achieve comparable accuracy to the original model. This is because the top-1 probability from the original model is dominant in computing the top-1 probability for the vocabulary-reduced model in Algorithm 2
K =
K = 2
K = 10
K = 50
K = 250
K = 1250
Bytes
78.09
66.34
53.30
48.82
50.19
47.61
Bytes
79.30
67.70
51.48
50.11
50.19
49.66
Bytes
78.54
67.85
53.45
51.18
49,20
48.37
8 Bytes 79.08
68.01
54.13
49.43
49,43
49.36
Original
47.54
Table 13: Accuracy on GSM8K by random sampling (with temperature 1.0) from Falcon3-7B with various top- K approximation of Algorithm 2 The accuracy nearest to the original one is shown in bold. In contrast to the case of greedy decoding (Table]12), we can see that a larger K required to approximate the behavior of the original model distribution.
D.7.2 EFFECTS ON ENSEMBLE RESULTS
K 1
K
K 10
K 50
250
K 1250
Owen2.5-0.5B OLMo2-1B 1B
29.49
38.06
39.42
39.35
39.50
39.42
Qwen2.5-3B & Falcon3-7B
75.66
80.59
80.67
80.89
80.82 61.87
80.97
Phi2-3B & Yi1.5-6B
45.56
59.59
61.71
61.56
61.79
Table 14: Ensemble results on GSM8K with various top- K approximation of Algorithm 2 employ greedy decoding in the same way as Section
Here we
22

---

Published as a conference paper at ICLR 2026
D.7.3 EFFECTS ON COMPUTATIONAL OVERHEAD IN ALGORITHM
3wen2.5-3BB (1 Bytes)
K-10
Counts
K-50
200
100
2.00
Steps
Bytes!
K-2
200
K-10
Counts
K-50
K-250
200
30
60
90
120
150
180
21.0
240
Steps
Qwen2.55 5-38 (4 Bytes)
K-10
Churts
K-50
K-250
200
0-
120
160
Falcon3-78 78 (1 Bytes)
400
K-10
Counts
K-50
200
Stops
Falcon3-78 Bytes)
Km2
200
K-10
Counts
K-2
200
0
40
80
120
160
200
240
210
Staps
Falcon3-78 Bytes)
K=2
K-50
K-250
3.00
1.00 125
150
Figure 4: We plotted the numbers of all summands (Counts) for computing each next-token distribu- tion of the vocabulary-reduced model in Algorithm (lines 11 and 16), averaged over 100 generations for each token position (Steps). In other words, these results indicate how the actual computational overhead of Algorithm 2 varies by the choice of the hyperparameter K. The dotted line shows the number of top- K probabilities (line 16) which exactly equals to K by definition, and the solid line shows the total number of added probabilities including the past ones (line 11). The results imply the overhead is bounded by relatively small number with respect to K, except for the first few steps in generation.
23


Reviews:
[{"review_id": "VLDmFv1arr", "reviewer": "Reviewer_ZBoh", "summary": "This paper introduces Lossless Vocabulary Reduction (LVR), a method to convert an autoregressive language model's next-token distribution into an equivalent distribution over an arbitrary sub-vocabulary $\\mathcal{V}_{sub}$. The authors prove that this reduction is lossless and propose the Maximal Common Vocabulary (MCV) method for model ensembling, which is both computationally efficient and empirically effective.", "questions": "Q1:  Could you provide a more detailed analysis of the computational overhead of Algorithm 2? For example, What is the typical size of the relative cover set $C_{\\mathcal{V},\\mathcal{V}_{sub}}$ during generation? How does it grow with the sequence length $k$?\n\nQ2: In Table 1, the Falcon3-7B model shows significant fluctuations in the reported metrics when the maximum token length is ≤ 2 bytes. Could the authors further analyze the factors driving these metric variations? Specifically, is the observed instability attributable to the approximation algorithm used?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "S1: This paper presents a theoretical framework to losslessly reduce a language model to an arbitrary sub-vocabulary. This is a strong, novel, and highly significant theoretical contribution that generalizes prior work, which was limited to byte-level reduction.\n\n\nS2: The proposed LVR framework, especially the MCV ensemble application, provides a principled and effective solution, achieving the theoretical correctness of byte-level reduction while offering superior generation efficiency.\n\nS3: The authors conduct well-designed and clearly presented experiments, which directly support the paper's core claims.", "weaknesses": "W1:  The Algorithm 2 still requires iterating over the relative cover set $C_{\\mathcal{V},\\mathcal{V}_{sub}}$  and the top-K tokens of the original vocabulary $\\mathcal{V}^{(K)}$. The authors should provide a more detailed complexity analysis (both Algorithm 1 and Algorithm 2), for example, discussing the size of the relative cover set and the overall computation complexity.\n\n\nW2: The Algorithm 2 introduces a top-K approximation, which technically breaks the \"lossless\" guarantee of the core theory. While the Table 1 show the performance is \"almost lossless\", the sensitivity to the hyperparameter $K$ (set to 300 in experiments) should be discussed.\n\n\nW3: Since the proposed Maximal Common Vocabulary (MCV) method can be regarded as a generalization of byte-level reduction, and its performance is largely determined by the size of the common vocabulary, the authors should provide a simple analysis the common-vocabulary sizes of tokenizers used in widely adopted LLMs. Such an analysis would provide an intuitive quantification of the extent to which MCV improves over byte-level reduction.\n\n\nW4: Because the current MCV ensemble approach appears to be strongly dependent on the model family (i.e. the tokenizer), the authors should evaluate a more diverse set of model families and additional ensemble configurations to further validate the advantages of their method. Expanding the range of models and ensemble combinations is likely to produce more pronounced and convincing results.", "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": "F21NuLJc9g", "reviewer": "Reviewer_j2YE", "summary": "This paper introduces Lossless Vocabulary Reduction (LVR), a method designed to reduce the size of subword vocabularies while maintaining full reversibility to the original tokenization. The key idea is to perform deterministic merging and re-encoding of redundant subwords, enabling significant vocabulary compression without retraining or modifying existing tokenizers.", "questions": "1. How does LVR affect inference efficiency (e.g., wall-clock time, FLOPs, or memory usage) given the longer token sequences?\n2. Is there a practical limit to vocabulary reduction beyond which sequence length growth harms model throughput or accuracy?\n3. How are special tokens ([CLS], [SEP], , etc.) handled — are they exempt from reduction or transformed within the same framework?\n4. For large pretrained models (e.g., GPT, T5), how easily can LVR be retrofit into production pipelines, and are there compatibility concerns with cached tokenizers?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper tackles a well-known bottleneck in NLP efficiency, oversized vocabularies that inflate embedding and softmax layers. A lossless solution that requires no retraining is both innovative and practically relevant.\n2. The authors provide rigorous proofs ensuring bijective mappings between reduced and original vocabularies. This formal treatment gives confidence that the method is safe for use in production systems where reversibility is critical.\n3. The method can be applied to any existing subword vocabulary without altering model architecture or retraining steps. This post hoc compatibility makes it very attractive for deployment in pretrained LMs.", "weaknesses": "1. The paper does not compare LVR with recently proposed learned vocabulary reduction or adaptive tokenization approaches, which may achieve similar goals via training-based optimization.\n2. Experiments focus mainly on LM perplexity and simple classification benchmarks. More diverse downstream tasks, especially those sensitive to segmentation (e.g., NMT, summarization)—would make the validation more comprehensive.", "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": "0EL4G2rBaj", "reviewer": "Reviewer_m5ZA", "summary": "This paper presents a framework for lossless vocabulary reduction with detailed theoretical guarantees, showing that for an auto-regressive language model, the reduction does not lead to any performance loss, and it is more efficient compared to byte-level reduction methods.", "questions": "1.In the experimental section, the authors present ensemble results using Qwen2.5-3B and Falcon-7B. Given this, could the authors also provide the individual vocabulary compression rates for Qwen2.5-3B and Falcon-7B, as well as a comparison of compression rates across different ensemble strategies?\n\n2.Different models have different tokenizers, which affects not only ensemble learning but also knowledge distillation, as mentioned in the Introduction. Could the proposed method be applied to knowledge distillation as well? If so, could the authors provide a possible application idea?\n\n3.A minor issue: the first half of the abstract overlaps too much with the first paragraph of the introduction.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper is theoretically grounded, with rigorous and well-structured proofs that justify the correctness of the proposed approach. Moreover, the method is motivated by a clear intuition and contributes a novel perspective to the problem of vocabulary reduction in language models.", "weaknesses": "1.The \"An illustrative example\" in Section 3.2, the example might not be presented in the most effective format. The use of a visual illustration or an alternative narrative style could potentially improve clarity and readability.\n\n2.The authors only provide experimental results on vocabulary reduction over GSM8K and a single ensemble setup. This might be somewhat limited in terms of empirical evidence, and the experimental section could benefit from broader evaluations to more convincingly support the method’s effectiveness.", "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": "CXDYt60qQy", "reviewer": "Reviewer_zQB1", "summary": "The paper proposes a general framework for lossless vocabulary reduction (LVR) that converts any next‑token distribution over a vocabulary into an equivalent distribution over an arbitrary sub‑vocabulary. The key construct is nested tokenization defined by first tokenizing into $V$ and then retokenizing each token’s byte string into $V_{\\text{sub}}$. The induced distribution $p_{V\\to V_{\\text{sub}}}$ is shown to be lossless at the text level. The authors propose lossless vocabulary reduction (LVR), by giving a computable recursion for the marginal probabilities via relative covering sets, and then presenting an efficient approximation reuses cached covers and probabilities and restricting the inner loop to top‑K tokens. On top of the analysis, the authors introduce ensemble via maximal common vocabulary (MCV), formed by intersecting vocabularies and restricting BPE merges accordingly. Experiments show that LVR preserves accuracy on GSM8K compared to the original model and substantially outperforms baselines. The method also helps to ensemble two models with different vocabulary.", "questions": "Please refer to weaknesses", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. **Rigorous theoretical analysis.** The paper precisely defines and states tokenization with an appropriate symbol framework. On top of the framework, the paper clearly proposes the LVR with rich theoretical demonstrations and proof.\n2. **Clear demonstration.**  The binary toy example helps to understand “lossless text distribution but different greedy path” phenomenon.\n3. **Experimental results.** On GSM8K, LVR closely matches or slightly exceeds the original model across different vocabulary settings, whereas Naive Restriction fails badly, demonstrating the effectiveness of the method.\n4. **Successfully applied to model ensembling.** The proposed method successfully ensembled different language models with different vocabularies, showing application values for other research fields.", "weaknesses": "1. **Overclaim on \"lossless\".** Theorems guarantee exact text‑level equivalence, while Algorithm 2 introduces two approximations such as the top‑K truncation. There is no error bound tying those approximations to the final possible \"loss\" incurred. The result is that “lossless” in practice becomes “almost lossless,” but the gap is unquantified. \n2. **Limited model pairs compared.** Only one pair of model ensemble is examined in the paper. Results on more models pairs, tasks, or even working languages are recommended. \n3. **No perplexity or likelihood evaluation.** Since the claim is distributional equivalence, perplexity/negative log‑likelihood curves before/after reduction would be the most direct metric. The current focus on task accuracy is informative but indirect.", "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)