Exact Byte-Level Probabilities from Tokenized Language Models for FIM-Tasks and Model Ensembles
Authors: Buu Phan
Brandon Amos
Itai Gat
Marton Havasi
Matthew J. Muckley
Karen Ullrich
Venue: ICLR 2025 Poster (2025)
Keywords: Language models
Tokenization
Probability
Sampling
Primary area: foundation or frontier models, including LLMs
TL;DR: We describe an algorithmic process to turn any tokenized LLM into its statistically equivalent byte-level LLM. Applications; FIM task + model ensembles.

Abstract: Tokenization is associated with many poorly understood shortcomings in language models (LMs), yet remains an important component for long sequence scaling purposes. This work studies  how tokenization impacts  model performance by analyzing and comparing the stochastic behavior of tokenized models with their byte-level, or token-free, counterparts. We discover that, even when the two models are statistically equivalent, their predictive distributions over the next byte can be substantially different, a phenomenon we term as ``tokenization bias''. To fully characterize this phenomenon, we  introduce the Byte-Token Representation Lemma, a framework that establishes a mapping between the learned token distribution and its equivalent byte-level distribution.  From this result, we develop a next-byte sampling algorithm  that eliminates tokenization bias without requiring further training or optimization. In other words, this enables zero-shot conversion of tokenized LMs into statistically equivalent token-free ones. We demonstrate its broad applicability with two use cases: fill-in-the-middle (FIM) tasks and model ensembles. In FIM tasks where input prompts may terminate mid-token, leading to out-of-distribution tokenization, our method mitigates performance degradation and achieves 18\% improvement in FIM coding benchmarks, while consistently outperforming the standard token healing fix. For model ensembles where each model employs a distinct vocabulary, our approach enables seamless integration, resulting in improved performance up to 3.7\% over individual models across various standard baselines in reasoning, knowledge, and coding. Code is available at:https: //github.com/facebookresearch/Exact-Byte-Level-Probabilities-from-Tokenized-LMs.

Published as a conference paper at ICLR 2025
EXACT BYTE-LEVEL PROBABILITIES FROM TOKENIZED LANGUAGE MODELS FOR FIM- TASKSASKS AND MODEL ENSEMBLES
Buu Phan"*, Brandon Amos", Itai Gat', Marton Havasi", Matthew Muckley", Karen Uilrich²
University of Toronto, Meta Al truong phan@mail www..l.tooooooooo.o ca (bda, itaigat, marton, mmuckley. karenu)emeta.com
ABSTRACT
Tokenization associated with many poorly understood shortcomings in language models (LMs), yet remains important component for long sequence scaling purposes. This work studies how tokenization impacts model performance by analyzing and comparing the stochastic behavior of tokenized models with their byte-level, or token-free, counterparts. We discover that, even when the two mod- els are statistically equivalent, their predictive distributions over the next byte can be substantially different, a phenomenon we term as "tokenization bias". To fully characterize this phenomenon, we introduce the Byte-Token Representation Lemma, framework that establishes mapping between the learned token dis- tribution and its equivalent byte-level distribution. From this result, we develop a next-byte sampling algorithm that eliminates tokenization bias without requiring further training or optimization.
other words, this enables zero-shot conver- sion of tokenized LMs into statistically equivalent token-free ones. We demon- strate its broad applicability with two use cases: fill-n-the-middlee (FIM) tasks and model ensembles. In FIM tasks where input prompts may terminate mid- token, leading to out-of- distiributiti tokenization, our method mitigates perfor- mance degradation and achieves 18% improvement in FIM coding benchmarks, while consistently outperforming the standard token healing fix. For model en- sembles where each model employs distinet vocabulary, our approach enables seamless integration, resulting in improved performance up to 3.7% over individ- ual models across various standard baselines in reasoning, knowledge, and cod- ing. Code is available at: httpggghww.ooooecccoooeeeeee///e Bateectt-ttteeeelll Probabilities -eabbiittessfrom---- from-Tokenizedd Tokenized-LMs.
INTRODUCTION
Transformers form the backbone of all widely-used state-of-the-art language models (LMs) such as GPTs (Brown al., 2020), Llama (Touvron al., 2023), ans Mistral (Jiang et al., 2023a). A com- mon pre-processing step in these models is tokenization, a method that shortens the input sequence by mapping multiple bytes, i.c. characters into discrete tokens, i.c. words or subwords, from fixed vocabulary Efforts to bypass tokenization have shown limited empirical success (Yu et al., 2024; Limisiewicz al., 2024), suggesting tokenization is critical to the performance of large language models (LLMs). It has been speculated that the reason for the performance gap between tokenized and byte-level models due to the reduction of input tokens, allowing models to handle longer con- texts less compute (Zouhar al., 2023; Goldman al., 2024). Recent work by Rajaraman et al. (2024) provides an additional explanation: Even for unlimited data and compute' 2, tokenized models achieve better cross-entropy loss than untokenized ones, resulting in superior performance.
WWok done during internship at Meta AL. In the context of this study, from subset of the tokenization vocabulary. This subset is somewhat flexible. Precision only important the experiment section where we define the subset to be all utf-8 bytes. be approximated 8t order Markov chain.
the terms "character" and "byte" interchangeably to refer to element
And assuming the data

---

Published as a conference paper at ICLR 2025
Prompt
de. add5 socuzn
Next-Byte Prediction
Noxt-Tokan Prodiction
Exact Byte Prediction (Ours)
Prediction
Tokan
Probability
Byte
Probability
Token
Probabbility
0.5
Sxpor
Byte
YE
Protsbbllty
0.01
0.02
0.5
0.5
Syte
Ensemble Method
of Choice
Probubility
Convension
Fp
0,11
0.9
Token
Probability
0.5
Byte
Probability
A
0.3
Jef add5 X retuzr
She add55 setuun
V
0.5
RA 0.2
Figure/ 1: Left: Tokenized LMs can experience tokenization bias when prompts end mid-token, as in this code completion example. This means that the correct solution, has zero probability of being chosen. Our method avoids this problem and can predict the correct token while using the same model. Right: Our method maps next-token predictions of arbitrary tokenized LMs statistically equivalent next-byte predictions (see Section 1 for details). This enables any model ensemble strategy, such as averaging or mixture of experts.
To contribute to the understanding of the impact of tokenization, we demonstrate that for any to- kenized LM, there exists a statistically equivalent byte-level process. Despite this fact, we find surprising discrepancy in their predictive Sabbavorrs-paricullaae in next-token and next-byte pre- dictions, where there can be significant differences. We hence introduce the concept of tokenization bias to describe the discrepancy between the predictive distributions of the tokenized model and the byte-level equivalent. Towards mapping tokenized predictions to byte-level predictions, we present the Byte-Tokkn Representation Lemma (Section 4.1). This result enables both byte-level predictions and an algorithmic correction of tokenization bias in any trained LM without the need for additional training optimization, allowing us sample bias-free next-bytes from any tokenized LM.
Since tokenization bias limits certain token combinations and impairs the model's ability to sample specific tokens, it is especially detrimental for tasks such as coding, where precise completion is necessary. We focus on fill-in-the- the-middle (FIM) tasks, where tokenization bias poses significant challenges, particularly when prompt ends mid-token. Previous research (Dagan al., 2024) highlights this issue, showing that language models struggle to generate the correct completion in such cases. Our theory predicts this phenomenon precisely, and the failure example shown in Figure (Left) can be reproduced with any open-wes open-weight model to date. Our experiments show that our next-byte prediction method outperforms tokenized models with the same cross-entropy by 18%, and is able to corrects cases where specialized fixes, such as token healing/alignment (Dagan et al., 2024; Roziere al., 2023; Athiwaratkun et al., 2024), consistently fails backup.
A byproduct of our byte-level prediction algorithm is that it enables ensembling of arbitrary LMs. Ordinarily, one cannot average the predictions of LMs that not share a vocabulary. By map- ping their predictions and conditioning domains to byte-space, one can easily aggregate predictions from multiple models and leverage the benefits of ensembling. Combining multiple models is ad- vantageous because ensembles are generally more accurate and robust than any individual member (Hastic et al., 2009). We confirm this empirically: ensembling LMs with our byte-level predictions outperform individual models in many cases. Overall, the key contributions of this work are:
1. We convert tokenized LMs into statistically equivalent loken-free models, and demonstrate that their predictive distributions differ. We define this discrepancy as tokenization bias.
2. We introduce method that enables next-byte prediction for any tokenized language model to fully mitigate tokenization bias. This algorithm is applied at inference time and carries O(1) computational cost in terms of model runs.
3. We present strong empirical evaluations on FIM benchmarks (18% improvement) and model ensemble tasks (up to 3.7% improvement), further demonstrating the effectiveness of our approach.
NOTATIONS AND SETUP
2.1 STRING AND BYTE-LEVEL LANGUAGE MODELS
We denote the alphabet set as A and its element character, or byte, as x. By default and consistent with real-world data, unless otherwise stated, include the end of string <BOS> byte in A. For any
(finite) string 8, we denote its substring from location i to j as x == 170141-... We view any byte-
2

---

note that in general, Published as a conference paper at ICLR 2025
level LM discrete stochastic process that defines the autoregressive probability P(zx+11 (=?) for all n. This defines an infinite (stochastic) sequence x = 21 where X E X. With the existence of <EOS>, we have P(z++1/27) = 1.0 for 2n+1 2n =<EOS> and P( <EOS>|a7) # 0.0 for any 21. Effectively, x have finite length and the set is countably infinite. We refer to x as byte sequence instead of a string, which has finite length and does not necessarily end with <EOS>.
Given 27 the function prefix(.) returns all possible prefixes of 27, i.e. profix(=") = (xi, a ... ". We denote the concatenation operation concat(.), i.e. concat(<" vi ) Ti Mt M/n. We define (xT) as the set of all byte sequences x with prefix æ;, i.e.
i.e.
{x|=" E prefix(x)),
which corresponds to the byte-level probability of obtaining a sequence with prefix 27, or P(x7).
2.2 TOKENIZED LANGUAGE MODELS
We consider two commonly used tokenization algorithms, namely Byte-Pair Encoding (BPE) (see Algorithm in Appendix A.4) and Maximum Prefix Encoding (MPE). Tokens are elements within vocabulary V. where A V, an individual token is denoted E V. We also assume <EOS> not part of any token but itself. An encoding consisting of & tokens of a string 2 is t encode(x") ) Conversely, a decoding of t is string denoted as z decode(tf). Encodings with an unspecified number of tokens are denoted as f' and [(t:)] are the elements from to j of f. Note that BPE and MPE are deterministic, i.e. each string and sequence x correspond to a unique encoding. We define (th) as a set consisting of all sequences whose encodings start with tf. i.c.
X((t)) fx| = encode(x))),
which corresponds to the token-level probability P(t"). i.e the probability of obtaining a sequence whose encoding starts with tf. We also view any tokenized LM as an autoregressive process that defines P(4++1 ((+) and refer to an infinite token sequence as t= 11/2.. and t E T. Similar as the
byte-level process, with the existence of <EOS>, effectively finite and T is countably infinite.
3 LANGUAGE MODELS AND TOKENIZATION BIAS
3.1 STATISTICAL EQUIVALENCE BETWEEN DATA GENERATING PROCESSES
We begin by establishing the definition of statistical equivalence between two stochastic processes. Then, show that byte-level LMs and their induced tokenized LMs are statistically equivalent. Definition 1. (Statistical Equivalence) For a countably infinite set X, the byte-level data generating processes Gi and G2 statistically equivalent if and only if:
Pg. (x) Pg, (x) for all x X,
i... the chance of sampling identical for processes G1 and G2. denoted by their subscripts. We consider the following two stochastic processes:
G1 the ground truth byte-level language models P(zn+1|2"))
G2 consists of the tokenized model P(tx+1lth) induced from the process G1 and tokeniza- tion. The process G2 generates sequence by autoregressively sampling new f441 and maps fx+1 to its byte-level representation using the decodo(.) function.
Since every sequence maps unique encoding t=encode(x) that again maps to the same x. we have P(x)==(tt) and thus Pg, (x)=Pş, (x) or two processes are statistically equivalent. This correspondence is unique because must end with <EOS>. Importantly, P(x+) * P(encode(z")), as there exist other encodings in addition to encode(x?)) sharing the same prefix =/. Nevertheless, this establishment implies that tokenized LMs can be converted into a statistically equivalent byte-level counterpart.
3.2 TOKENIZATION BIAS
Despite their statistical equivalence, the generation behavior of tokenized and byte-level LMs can be significantly different when prompted with the same string. We characterize the tokenization bias phenomenon that describes this discrepancy between conditioning domains, i.e. bytes versus tokens.
3

---

Published as a conference paper at ICLR 2025
(1-a)²
1-8
AA
B
Token Vocabulary
(1
(1-8)8
0.0
B
1-8
ID
Token
a(l-a)
1.0
1
A.
9
2
3
AA
Input Prompt: "AABABAA"
BPF/ MPF
Output Tokens: "AA|S|A|B|AA"
Tokenization bias -rddr Markov chain. Given the context token "A", the model will never sample the next token as "A", rather than with probability a. In practice, this bias occurs when prompts end with tokens that are part of another token, common issue in the FIM lasks, leading to incorrect completions by the model.
Figure 2:
Definition 2. (Tokenization Bias) Let the input prompt 2i have the corresponding encoding 1 ===cncdde(ff). ( The tokenization bias occurs for this prompt when:
P(zn+ilaf) + P(In+1ltf),
(1)
where (144) Eies P(1+-1=11()) and & (1 V|sn+1 decode(())): i.e. the set of tokens whose first byte is In+1-
For example, the probability of the next byte being "cc" may be different from the sum of the prob- abilities of all tokens that start with "c", which offers a broader perspective compared to the proba- bility of the subsequent token being exactly "c"
3.2.1 TOKENIZATION BIAS IN MARKOV CHAINS
To systematically study tokenization bias, we employ a simplified autoregressive model, represent- ing the data generating process Markov chain. As result, we can derive a closed-form expres- sion for the induced tokenized model and directly observe the tokenization bias phenomenon.
We consider 1st order Markov chain with states {"A", "B"), shown in Figure (left) where each string is tokenized with either MPE or BPE, which yields the same result. With the vocabulary {AAA", "A", "B" }. we obtain new Markov chain whose states and transition matrix are shown in Figure 2 (right). Appendix A.7 provides details on computing the transition matrix. The statistical equivalency between two chains is described in Rajaraman et al. (2024). First, notice that no tokenization bias occurs when conditioning on 1 = "AA" or t = "B", e.g.
"A" P(x3= "A" [ "AA") = P(|== "AA" "A=="AAA)>> + P(|2="A||<==>
= a
However, when conditioning on "1= tokenization bias emerges, i.e. the probability equal to P(rz="A" [|r)== Markov chain never samples "A" with any prompt ending with token "A". The reason is that whenever two consecutive bytes "A" appear together, the tokenizer immediately merges them into single token "AA", results in probability. Despite being simple, this model portrays the exact phenomenon as the coding example discussed in Figure (Left).
Ground Trut: Pir. Our Bias Cerrection Method Biased Estimater P/ PI)
is not 1-a, i.e. the token-level
88/
BA8
3 Bytos
BM
A38
ABA
Higher-Order Markov Chain. We now show this phe- nomenon in more complex, 3rd order Markov chain, but shift from mathematical derivation to an empirical approach to demonstrate its relevance practice. Furthermore, we lever- age this example to illustrate the effectiveness of our byte- token conversion method, to be introduced in Section 4, as a viable bias correction technique. Here, we train decoder transformer on tokenized data and analyse its next-token prob- abilities, shown in Figure 3. As expect, the trained tok- enized model exhibits severe bias in its predictions. Neverthe- less, when combined with our bias correction technique, accurately recover the original transition probabilities, demonstrating its potential for generalization to other LMs. We detail the experiment setup in Appendix A.7.
M48
0..
Probabiiity of Next Byte being A
Figure Tokenization bias on 3rd order Markov chain. Our byte- token conversion (bias correction) method in Section 4 accurately covers P [xT) of the original chain.
4

---

Published as a conference paper at ICLR 2025
Representation of ((T)) under Language Model (ftxiit)
P(s)=
= Σ P()
Algoritim
Efficient Aigorithm Cover Encodiigg: by
Backward Tokenication
ercodee ureodu""usat")
Quary String (u m 5)
Vocabulary V
ID
Tikesa
Paration
X
y
Rical rokees fi-.
Cover Encodings (Ecover(af")
woooting ming
y2
anooda
startwith "ay"
0-g
m
m
y
the contired encoding
B.
21
Froonting
ancoco
Last taken cancitanse
encundel yyu?
Tokens startwtth "rang""
Acoope/Rcjott
Oriooio
Inveled Eneoddrn
Figure 4: Left: Representation of P(æT) using tokenized LM with an example of cover encodings and valid/invalid encoding. Right: Illustration of Algorithm for cover encodings search. Green tick and red cross denote valid and invalid encodings respectively (Definition 3). The termination step can be easily implemented despite shown in the algorithm. We use BPE in this example.
3.2.2 INVALID ENCODINGS
The investigation the probability events observed in Markov chain example leads us to introduce the definition of invalid encodings, which sets constraints the probability P(i) of tokenized LMs. We remind the readers that this definition specifically targets BPE/MPE.
Definition 3. (Invalid Encodings) An encoding I is invalid under BPE/MPE encoding scheme encode(deccdde()))f. else it valid.
In other words, invalid encodings represent the string with different tokens than the one produced by the tokenizer. For example, assume MPE tokenizer and V= "c" "a", , "t", "at", "cat"). then encode( "ctt""t""""""" """aat"""""""" "t"]. Encodings ["c", "at", ""at"""""] and ["c", "a", "a",tt "t", "t"] are invalid.
With this definition, Proposition I states that invalid encodings will exist in the token distribution. Proposition 1. X
= Ø if and only if 1 is invalid. As result, P(t)) = 0.0. Furthermore, P(tyle k- 0.0 if 1 is valid, otherwise, it is undefined.
Proof. See Appendix A.4
Remark 1. Proposition 1 indicates the constraints of P(tt) for tokenized LM induced by the byte- level data generating process. For trained LMs, P(tglth-1) for invalid t due softmax tivations but observe it to be very low compared to the valid t similar to those in Figure 3. Since invalid encodings are provably non-existent in the ground-truth token-level distribution, we truncate these invalid probabilities tailed Appendix A.6. From now, we assume that the LMs will assign zero probability to provably non-existent encodings in the token-level distribution.
without any loss in terms of perplexity score, de-
EXACT BYTE-LEVEL PROBABILITIES
4.1 BYTE-TOKEN REPRESENTATION LEMMA FOR P(=))
To addresses the tokenization bias, we derive byte-level predictions P(I.+1 [ from token-level predictions P(1++1 ( this end, we compute P(x])) and begin with concept of cover en- codings of xT. These encodings are valid encodings that "optimally" contain z1, iec their last tokens start at locations < n. Results in this section, i.c. Section 4.1, apply for any deterministic tokenizer, not just BPE/ MPE (also Remark 1).
Definition 4. (Cover Encodings) Given prefix æf. an encoding e is said to be covering xf when all the following conditions are satisfied:
X(tt) * (i.c. t is a valid encoding in the case of BPE/MPE).
2. There exists index such that x prefix(decode(4.)) and decode af-1 where i & n, i.e. decode(t?) starts with xt and the last token 4 covers suffix of x...
5

---

Published as a conference paper at ICLR 2025
We denote cover(zf) to be the set of all cover encodings of of,, with examples in Figure (mid-left).
We now establish the BTR Lemma that allows us to exactly compute P(z]) from ((fx+1/tf)) The main idea is that for any sequence x starting with zf. its encoding encode(x) must start with one of the encodings in cover(æ") (..).
Lemma 1. (Byte- Token Representation) For a language model P(1++1l()) given a prefex of, the following statements hold:
1. For any distinct E, cover(xt), we have n(0))
2. X(x7) = (T))
TEcover(x?)
As result, P(xt) can be expressed as the marginal probability of all covering tokens of at
P(at) = E
P(t).
(2)
(εcover(z})
Proof. See Appendix A.2.
Remark 2. The BTR Lemma provides a general view of tokenization bias. Consider the cover en- coding example in Figure 4 (middle-left). There, given the input string of "yummy", prompting into the models encode(z;) (x]] = ["yum", "my"" will discards the other two possibilities, resulting in skew distribution over the next-byte, ie. tokenization bias.
Some scenarios requires conditioning special tokens, such when using control/synthetic tokens (e.g.. FIM rode-infilling. In such cases, we want to compute the byte-level probability conditioned on specific tokens, i.e. P( +1 ((f) where x/' decode(tf). equivalently, P(xf, 14). Corollary provides closed-form expression for this quantity.
Corollary 1. We can express P(If, tf) where decode(th) E prefix(zf) as follows:
P(
Σ
P(P),
PEcover(aç)
i.e., to compute P(rT, t4), we limit the set of cover encodings to those that starts with th.
Proof. See Appendix A.3.
Finally, applying Lemma requires searching all cover(x;)) which can be time-consuming with naive search. For the tokenizers under consideration, i.c. BPE and MPE, there exists an efficient algorithm by using the properties of invalid encodings (Definition 3), explained in Section 4.1.I.
4.1.1 COVER ENCODING SEARCH ALGORITHM
We present the cover search process for BPE/MPE in Algorithm 1, which is illustrated in Figure 4 (right). Note that the algorithm also returns P(t) for E cover(rf) which we will use to sample subsequent characters later on. The idea follows: instead of searching for cover encodings from left to right, which can be computationally expensive, we search for valid encodings in reverse order, starting from the right. Suppose the last token 44, of cover encoding t is known and it has suffix 2ft1 then according to Proposition 1, we must have: / -encodee(ee(() (x]), else if will be invalid.
As result, searching from the reverse order, for any suffix x/i1, we can find all tokens that start with 2a+11- tokenize zi and check if their combination is valid or not. The number of model runs is at most nf, where is length of the longest token in V. order to compute P(t). In practice, the actual number of inference runs is much lower since encode( (xf) of the current iterations often contains encodings of the later iterations. Finally, while we can obtain P( [>f) through factorization using this algorithm, it is not practical for sampling purpose
need to repeat the process for all In+1 E A. We next show an efficient alternative in Section 4.2.

---

Published as a conference paper at ICLR 2025
Algorithm (Cover Encodings Search). Compute P(xf) and P(() for each (Ecover
1: procedure EXTRACT, EXTRACT_COVER(C COVER(:;))
2: cover dict 0 Dictionary {T: P(O)
3: for i n ..... 0 do
4:
# Find all tokens covering r;+1 and tokenize the remaining z1 (dreeix((ecode(()))
5:
B = {t E
6:
1 -enode((1))
7:
# Compute P(tf) where of 11, all t V
8:
P(tt) P(th-1) 1)x P(tx+1 t/th-1) ) # Broadcast Multiplication for all
9:
# Remove invalid encodings.
for / E do = concati (=k-1_ cover diet 8 P(t) if valid(
11:
12:
end for
14: end for
co)er(at) = cover dict..eys()
16:
P(xf)= Σ P(E) # from the BTR Lemma Lemma 1).
:Erower dict.
17:
return P(zf), cover dict
18:
end procedure
4.2
EFFICIENT NEXT- SAMPLING ALGORITHM FOR P(In41 | xxf)
To efficiently compute P( ( for any #n+1=a A, note that cover(x;* contains:
C,+1(a): encodings E from the previous cover(2ff) whose (n 1)th bytes is Formally, we have: (o (decoode =a].
C (a): encodings 7 whose last token starts with a the (n 1) location. Formally, we have: Cn+1 (f decode((x+1) ==a].
Since (a) Cn+1 Ø, then:
P(* In+1 = a)
Σ P()++ Σ P(F).
Ca4i(a) Cn+ila)
With this formulation, we find cover(z)+1) following the process in Figure 5 (also see Algorithm in Appendix A.8). Specifically, to find Ca+1(a) and Ca+i(a) for every a E A, we:
1. Obtain cover(z?) using Algorithm or from Step 4 of the previous sample.
2. Find Cn+1 (a) by checking the (n + 1)th byte of each E'E cover(aT). We accumulate them for each a respectively.
3. Find C. (a) by querying the conditional distribution all tokens 7(4++1/4)) Note that P(I)) was already computed in cover(r?*). The encoding accept/reject step is optional.
4. Obtain cover(x])*) for all #n+1 A.
5. Sample 2x+1 from all computed P(=++1) (normalizing by P(x))).
Thus we only need to run Algorithm mapping of what tokens start with what bytes can be pre-computed and the sum over tokens can be parallelized via matrix multiplication. Also, one can avoid storing large number of encodings in Step 4 by sampling the next byte immediately after Step 3, following Equation (4), and only create the set of the sampled value Fx+1, i.e. Cn+1 (Ix+1).
the beginning of the sampling process. Step 3, the
Remark Computing P(x1²) requires accessing P(t but models such as the series (Young et al., 2024) do not provide P.t1). Nevertheless, it is possible to compute P(*x+1l22) (x") by leveraging
the pre-tokenization pattern such as white spaces or punctuation. Details in Appendix A.1.

---

Published as a conference paper at ICLR 2025
Sep Contan Cowe Fecadagg
Sap Zolfeguuung Trwwsur croddngeent lenert
Sinng Arrgl S
langth
Sangle
bngth
E
0910 m0
Dap
mrosag 18t beg pning ofth
Rccezsfliect
Sahan
owat youryn
n
Figure 5: Illustration of the sampling process for #n+1 from tokenized LM ((tx+1/t4) with exam- ple following Figure 4. We do not include P(t) for simplicity. Details in Section 4.2.
5 RELATED WORK
Algorithms for Tokenization Bias. Tokenization bias has been empirically observed when model produces unusual generations when prompted with string ends with trailing whitespace (Gao et al., 2023) or mid-word (Dagan et al., 2024). Token healing (Dagan et al., 2024; guidance ai, 2023) mit- igates this issue by searching for tokens prefixed with the incomplete word. This method, however, fails to consider all matching possibilities. In the "yummy" example in Figure 4, it can only recover two encodings "yum | my" and "yum myu" (tokens separated by "1"), as "my" is prefix string of tokens "my" and "myu", missing "yum m yum" (also see Appendix D). Similar techniques such as token-alignment (Athiwaratkun al., 2024) also failed address all underlying issues (see Ap- pendix E). Another proposed solution is using specific prompting strategies (Bavarian et al. (2022), also see PSM Mode in Section 6.1), requiring additional training and specific prompt structure. In contrast, we tackle the underlying issue by identifying the probabilistic root cause, i.e. the token- byte domain gap, and introduce a conversion technique to recover the unbiased byte-level distribu- tion without requiring retraining. Finally, Pimentel & Meister (2024) address different but related problem of computing next word probability, sharing some similar analysis but their approach is limited to peatesspacc-spprrttee tokenizers and does not support autoregressive byte sampling.
Language Model Ensembles To the best of our knowledge, our work is the first to (i) compute next token probabilities in a universal space for both input and output domains while (ii) guaranteeing that the statistical properties of all member models are preserved (see Section 4), and (iii) without the need for additional training, data or model modifications. Several works also attempted combine multiple LMs. Wan et al. (2024) introduce a model distillation technique by combining predictions from various LMs to fine-tune a primary model, which does not tackle the issue of vocabulary discrepancies. Jiang et al. (2023b) use ranking approach and evaluating outputs at the paragraph level and comparing them pairwise. However, their approach requires training a scoring function, making it sensitive to the distribution of training data and model choice. Huang et al. (2024) maps the token probabilities of member models to a universal space, which relies on token embedding's similarity and involves solving optimization task. Gu et al. (2024) also investigate character- level ensembling, but does not provide expressions for P(xT) or P(In+1|a)) and overlooks the issue of invalid encodings. Since their method condition on tokens without addressing the bias, it is susceptible to invalid encoding states and division by-zero errors, particularly with optimal sources.
EXPERIMENTS
6.1
CODE COMPLETION
Code completion with LLMs is well-suited for our byte-level predictions because the model is fre- quently prompted with incomplete code snippets. Here, we briefly introduce the setting and show that the byte-level predictions significantly improve upon the standard performance.
Fill-in-the middde (FIM) code completion. Code completion is the process of taking source code as input along with point in the middle to generate the completion, e.g., the point the user's cursor is at. So, generating new code in the middle does not fit into the standard autoregressive genera- tion provided by pre-training models, nor does it fit into standard systemm-usrr-ssssttan conversation prompt templates. The solution has been to introduce a fillin-the-mmidlle (FIM) prompt template that turns the middle generation back into a standard prompt that can be completed by an autoregres- sive model (Bavarian et al., 2022). These FIM prompt templates introduce sequences and cannot be used with a model that is not aware of them, so code models are then trained (or fine-tuned) dataset of code formatted into these FIM prompt templates.
tokens or control
8

---

Published as a conference paper at ICLR 2025
Byte-level
Token-level
PSM
SPM
100
Predictions
Greedy
@ 10
Greedy
@:
Token-level healing
64.9
84.0
45.0
66.5
62.7
83.8
alignment
63.0
82.9
60
PSM
SPM
SPM - healing
Byte-level 65.7
84.1
63,9
84.3
0.00
0.25
0.50
0.75
1.00
0.25
0.50 0.75
1.00
10 here is the max over the lemperature sweep on the right
Tempersture
Temperature
Figure 6: Pass rates for the HumanEval Random Span benchmark from Bavarian et al. (2022) with CodeLlama-7k for infilling Python. Across all settings, the byte-level predic- tions yield better completions. We evaluate the two standard infilling prompt templates of (PSM) and Peffix-Prefix-Midd.. use token healing (Dagan al., 2024) and alignment (Athiwaratkun et al., 2024). The SPM template forces the model to make predictions from the middle of a token, which our byte-level predictions successfully handle.
(SPM), and as baselines
Prompt templates for FIM. Given a (prefix) and (suffix) along with the control tokens <PRE>, <MID>, and <SUF>, there are two main prompt formats for querying code model to generate the middle portion: the Prefix-Suffix-M. ddle (PSM) format "<PRE> (prefix) <SUF> (suffix) <MID>", and Suffix-Preeix--.tddd ddle (SPM) format is "<PRE> <SUF> (suffix) <MID> (prefix)".
Upsides and downsides of PSM and SPM. The default and most widely-used mode is PSM (Bavar- ian et al., 2022; Roziere et al., 2023). We speculate this is the default mode because there are no tokenization issues in it: the incomplete prefix is clearly separated from the middle portion to gener- ate by the control tokens. While the PSM format solves tokenization issues with this separation, the downside that it creates an unnatural separation between the prefix and middle generation. SPM mode overcomes this by prompting the model to generate immediately after the prefix, without any separating tokens. This contiguity is desirable as it would leverage more knowledge from the pre- training task, but now creates tokenization issue when the prefix stops in the middle of token. A standard heuristic to overcoming this in SPM mode is called token healing, e.g., as described Da- gan et al. (2024), but it does not correct every tokenization issue here. Another fix is token-alignmen (Athiwaratkun et al., 2024) but it is biased and suboptimal (see Appendix E). These issues make the PSM template outperform the SPM template in every previous results for code infilling.
Our results. We experimented with the standard random-span infilling benchmark from (Bavarian al., 2022). Figure 6 shows that our byte-level predictions in SPM mode attain superior perfor- mance when using 10 samples, using Code ama- 7b. This corroborates our hypothesis that the contiguity between the prompted prefix and generated middle in SPM mode is more natural and con- sistent with the pre-training objective of the model. Another surprising result is that the byte-level greedy generations outperform the token-level greedy generations.
Ablation This is surprising because each token typically spans over multiple bytes. hence for greedy generation the token model should have a slight advantage. We wanted to further investigate this finding and hence performed beam search with beam width 2 and 4, which led to consistent improve- ment of up to 2.9% and best performance at 67.7. The complete ablation is located in Appendix C.
6.2 MODEL ENSEMBLES
Ensemble methods rely on two principles; model prediction averaging (aggregation) and training each member of a model ensemble on a subset of all available data (bootstrapping). Ensemble methods are a popular choice because aggregation reduces the variance of the expected empirical test error, and bootstrapping reduces model bias. As a result, bootstrap aggregation leads to model ensembles that are generally more accurate and robust than any individual member model (Hastie et al., 2009). The recent surge of of available text, makes these LLMs ideal candidates for bootstrap aggregation.
LMs, each presumably trained on different subsets
Our method. Unfortunately, vocabulary discrepancies between LMs prevent direct aggregation, as models map to different token spaces. Our method solves this by enabling exact next-byte predic- tion, allowing any LM to map into the same space, so byte probabilities can be aggregated without restrictions on the aggregation function and preserving the statistical properties of the member mod- els. In this work, we choose simple averaging. We leave more complex methods for future work.

---

Published as a conference paper at ICLR 2025
MMLU
PIQA
NQ
TriviaQA
GSM8K
Model
Token
Byte
Token
Byte
Token
Byte
Token
Byte
Token
Byte
LL.ama2
45.4
45.7
78.1
78.2
25.0
23.4
58.4
58,1
15.1
12.5
Yi-1.
63.4
63.4
78.5
78.5
22.8
22.7
53.7
53.4
61.3
61.5
Kistral-7B-vol
62.1
62.1
80.1
80.3
28.5
28.8
63.6
63.5
39.0
39.0
Voting (top-2)
62.1
80.1
Top-2 ensemble (Our)
65.4
80.7
30.0
64.2
55.8
We evaluate the token and equivalent byte-level model performance of various open source LMs. We further show the byte-ensemble performance of the top-2 performing models. For all benchmarks but GSM8K, byte-level ensembles outperform single models and voting.
Table 1:
Benchmarks and setup. We compare next- token, next-byte, voting and byte-ensembles against one another on multiple knowledge, reasoning, and coding benchmarks. We chose our benchmarks due to their prevalence in test- ing general LM ability. Due to computational constraints, we test on 7B models primarily. Note that multiple choice tasks require likeli- hood evaluation (MMLU, PIQA) while other tasks require mid long generations. Finally, voting is not trivially extended to reasoning tasks without training an evaluator network.
Human Eval 69
MHPP@1
Model
Token
Byte
Token
Bytc
Lodellama22-
32.3
28.7
40.6
42.4
Codellama2-105
35.8
33,5
47.6
47.4
Yi Vi-Coder-1.4 1.8
38.4
36.5
52.8
53.6
Top-2 Ensemble
42.1
53.6
Table 2:
Token and byte-level performance of weigh code LMs. The byte-ensemble per- formance of the top-2 models achieves the best re- sults on the Human Eval benchmark while match- ing Yi-Coder-1 on MBPP
Our results. Results are shown in Table and 2. Byte and token predictions are on par with one an- other. Ensembling the top-2 performing models consistently lead to performance boost except when member model performance is too divergent, as in the case of GSM8K dataset where Yi Yi-1. 5- outperforms Mi
3, the second best LM, by margin of 20%. For coding tasks, the ensemble of Yi -il-Cder-11 5B and CodeLlamas dataset. Overall, these results showcase ensemble as an exciting direction for LMs collaboration.
improves up to 3.7% on Human Eval
7 CONCLUSION
Conclusion and limitations. This work shows that tokenized LMs have different predictive distribu- tions than their statistically equivalent byte-level counterpart, i.e. tokenization bias. We introduced an 0(1) next-byte prediction algorithm to mitigate this bias inference time and showed its empir- ical relevance for FIM benchmarks and model ensemble tasks. Yet, our method introduces notable memory consumption its current implementation, and incurs additional linear computational costs (one token multiple bytes). At present, these factors may limit its practical application in resource- constrained environments. While our work provides new insights into the effects of tokenization, not explain or mitigate all related phenomena such as poor performance arithmetic tasks.
Future work. While this work sheds some light on token- and byte-level LMs, several open ques- tions remain. Notably, our theory does not provide insight into the employed greedy evaluation process, nor do we examine the cumulative impact of tokenization bias. Regarding the latter, our analysis is limited single-token predictions, while real-world applications require generating hun- dreds of tokens. Building on our findings, future research can explore broader topics, such as bias- variance decomposition in LM ensembles, or interplays between bootstrapping and scaling laws. Another direction is model distillation, where larger models with larger vocabularies could be dis- tilled into smaller models with specialized tokenization. Our work can also enable prompt optimiza- tion, such as for universal adversarial attacks, and facilitates relative uncertainty estimation. Also, this work only scratched the surface of the possibility of model ensembles. For example, models trained separately on different languages may outperform single model trained all languages simultaneously, as they can achieve more optimal entropy bounds by leveraging language-spectin tokenizations. This might also improve the representation of otherwise underrepresented languages in a training data corpus. Finally, our results also open up new possibilities for tackling mechanism design problems (Duetting al., 2024) involving different language models, where the tokenization bias issue can potentially create unfair advantages for certain models.
8 ACKNOWLEDGMENTS
We thank Shubham Toshniwal and Jack Lanchantin for early comments and discussions.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Ben Athiwaratkum, Shiqi Wang, Mingyue Shang, Yuchen Tian, Zijian Wang. Sujan Kumar Gonu- gondla, Sanjay Krishna Gouda, Rob Kwiatowski, Ramesh Nallapati. and Bing Xiang. Token alignment via character matching for subword completion. arXiv preprint 2rXiv24033086688 2024.
Mohammad Bavarian, Heewoo Jun, Nikolas Tezak, John Schulman, Christine McLeavey, Jerry Tworek, and Mark Chen. Efficient training of language models to fill in the middle. arXiv preprint arXiv:2207. 14255, 2022.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
Gautier Dagan, Gabriele Synnaeve, and Baptiste Rozière. Getting the most out of your tokenizer for pre-training and domain adaptation. arXiv preprint arXiv:4402.01035, 2024.
Paul Duetting, Vahab Mirrokni, Renato Paes Leme, Haifeng Xu, and Song Zuo. Mechanism design for large language models. In Proceedings of the ACM Web Conference 2024, pp. 144-155, 2024.
L Gao, J Tow, B Abbasi, S Biderman, S Black, A DiPofi, C Foster, L Golding. Hsu, A Le Noac et al. A framework for few-shot language model evaluation, 12 2023. URL htips://zenodo. org/reconds/10256833. 7, 2023.
Omer Goldman, Avi Caciularu, Matan Eyal, Kris Cao, Idan Szpektor, and Reut Tsarfaty. Unpacking tokenization: Evaluating text compression and its correlation with model performance. arXiv preprint arXiv:2403.06265 2024.
Kevin Gu, Eva Tuecke, Dmitriy Katz, Raya Horesh, David Alvarez-Melis, and Mikhail Yurochkin. Chared: Character-wise ensemble decoding for large language models. arXiv preprint 2rXiv:2407.11000 2024.
guidance ai. Guidance ai, 2023. URL /tt.:t/tss////taab..co//uuuauue higgaaiaccc.///iiaa.e.... GitHub repository.
Trevor Hastie, Robert Tibshirani, Jerome H Friedman, and Jerome H Friedman. The elements of statistical learning: data mining, inference, and prediction, volume Springer, 2009.
Ari Holtzman, Jan Buys. Li Du, Maxwell Forbes, and Yejin Choi. The curious case neural text degeneration. 2020. URL https: //arxi/aaiiiiii wwtp://wwww.//a//////////// //t
09751.
Yichong Huang, Xiaocheng Feng. Baohang Li. Yang Xiang, Hui Wang, Bing Qin, and Ting Liu. Enabling ensemble learning for heterogeneous large language models with deep parallel collabo- ration. arXiv preprint arXiv:2404.12715, 2024.
Albert Q. Jiang et Mistral 7b, 2023a. URL
Dongfu Jiang, Xiang Ren, and Bill Yuchen Lin. Lim-blender Ensembling large language models with pairwise ranking and generative fusion. arXiv preprint 2.Xi::2300002661,, 2023b.
Philipp Koehn and Rebecca Knowles. Six challenges for neural machine translation. In Thang Luong, Alexandra Birch, Graham Neubig, and Andrew Finch (eds.), Proceedings of the First Workshop on Neural Machine Translation, pp. 28-39, Vancouver, August 2017. Association for Computational Linguistics. doi: 10. 1118655/11111-33200 URL https: htap::s://aclaathooogg..
oxg/x17-3204.
Tomasz Limisiewiez, Terra Blevins, Hila Gonen, Orevaoghene Ahia, and Luke Zettlemoyer. Myte: Morphology-driver byte encoding for better and fairer multilingual language modeling. arXiv preprint UrXiv:2403.106/ 2024.
Tiago Pimentel and Clara Meister. How to compute the probability a word. arXiv preprint arXiv:2406. 14561, 2024.
11

---

Published as a conference paper at ICLR 2025
Ivan Provilkov, Dmitrii Emelianenko, and Elena Voita. Bpe-dropout: Simple and effective subword regularization. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics. Association for Computational Linguistics, 2020.
Nived Rajaraman, Jiantao Jiao, and Kannan Ramchandran. Toward theory of tokenization in Ilms. arXiv preprint S4Xiv::20040033333 2024.
Baptiste Roziere, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Romain Sauvestre, Tal Remez, et Code llama: Open foundation models for code. arXiv preprint arXiv: 2308. /2950. 2023.
Felix Stahlberg and Bill Byrne On NMT search errors and model errors: Cat got your tongue? In Kentaro Inui, Jing Jiang, Vincent Ng, and Xiaojun Wan (eds.), Proceedings of the 2019 Con- ference Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 3356-3362, Hong Kong, China, November 2019, Association for Computational Linguistics. doi: 10. 10.18653/1/D119-1331
URL
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint 239771,, 2023.
Fanqi Wan, Xinting Huang, Deng Cai, Xiaojun Quan, Wei Bi, and Shuming Shi. Knowledge fusion of large language models. arXiv preprint arXiv:2401.1049/ 2024.
Alex Young, Bei Chen, Chao Li, Chengen Huang, Ge Zhang, Guanwei Zhang, Heng Li, Jiangcheng Zhu, Jianqun Chen, Jing Chang, al. Yi: Open foundation models by 01. ai. arXiv preprint arXiv:2403.044m 2024.
Lili Yu, Dániel Simig, Colin Flaherty, Armen Aghajanyan, Luke Zettlemoyer, and Mike Lewis. Megabyte: Predicting million-byte sequences with multiscale transformers. Advances in Neural Information Processing Systems, 36, 2024.
Vilém Zouhar, Clara Meister, Juan Gastaldi, Li Du, Mrinmaya Sachan, and Ryan Cotterell. Tok- enization and the noiseless channel. In Proceedings of the 61 Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 5184-5207, 2023.
12

---

Published as a conference paper at ICLR 2025
A APPENDIX
A.1 ESTIMATE p()n+1l07) WHEN P(()) IS NOT AVAILABLE
In practice, several models such as the Yi series do not provide P(t)) since does not include the beginning of sequence token. As a result, we cannot compute P(i). However, we can still compute P(z)-1 since their tokenization algorithm often force splitting words by using pre- tokenization pattern such as the whitespace. Let z; be the last whitespace byte in zं such that æ;-1 is not whitespace. Then we know that I encode(z1) must be the prefix encoding of all cover encodings of of. This holds not only for æf but also any string s = concat(x;; s') where s' is an arbitrary suffix.
As such, using the BTR Lemma I, we have:
P(z))= = Σ
P(T) P(tt) x EP(EIT)
(5)
REcover(a?))
('Ecover(2]
and hence, with factorization:
P(æn+1 (x+)
Σ
P(T)))
E p(T(t))
(6)
(Ecaver(a27t)
F (Ecover(=(4.)
which shows that we not need P(tt) to compute P(xT), ) since conditioning on them is sufficient. For autoregressive byte generation, condition each probability term in Algorithm 3 with ef.
A.2 PROOF OF LEMMA 1
Lemma 1. (Byte-Tokee Token Representation Lemma) For a consistent tokenizer and a corresponding language model P(tx+1|bH) given prefix 2/, have the followings:
For any distinct ī, cover(af), then x7) x(7)=0
2. X(=+) = xxx(),
(Ecover(a])
As result, P(xtt) can be expressed as the marginal probability all covering tokens of x/
P(xT)
P(O) (Ecover(27)
Σ
Proof. We prove each point follows:
1. Proof by contradiction, let 61,47 cover(uf) and of + f/ Suppose that there exists sequence where 1f encode(x){ and of encode(x), Without the loss of general- ization, suppose < j. then fff since our tokenizer deterministic. Hence, t cannot be cover encoding of x/.
2. This follows the definition of cover encodings.
Since each (t) is pair-wise disjoint, we arrive at the final equation.
A.3 PROOF OF COROLLARY
Corollary 1, We can express P(xf, 14) where decode(1t) E prefix(af)) as follows: Σ
P(2),14)
P(())
(8)
((cooer(xf))
# = [aa))
13

---

equivalently to proving t = t// for any Published as a conference paper at ICLR 2025
Algorithm 2 Byte Pair Encoding Algorithm.
1: procedure ENCODE ENCODE_BPECTT' V)
2: # Set initial encodings:
c_tokens x1
4: # Iterate over merging order V. the first [A] entries correspond the the alphabet (no merge happens):
5: for i=
A| + +,......1V> do
6: c_tokens + (nn..eergecc.tokens,, V(())
7: end for
return e tokens
9:
end procedure
10:
11: procedure meggofcegoc....knennn. v)
Left right tokens for merging
13:
tieft tright, fnew = v(1], x(2), old_tokens = c_tokens new rew_tokens
x2]), v(3)
14:
15:
16:
Find and merge tokens from left right
==
18:
while j < tokens/ do
19:
if old. tokens(i, i + 1] = hafts fright then
20:
new www.ess.ppeeedee..........
21:
j -
22:
else
23:
new www_tooens.aaao too.eeeessapppeolloooooellllll
24:
j= end
25:
26:
end while
27:
return new_tokens
28:
end procedure
Proof. The proof follows the one for the BTR Lemma I, where we only consider the cover encod- ings that start with 44.
A.4 PROOF OF PROPOSITION
For completeness, we first show the BPE encoding algorithm in Algorithm 2. For the MPE algo- rithm, the rule is greedily looking for the longest token that matches the prefix of the given text.
Proposition
x(tt) Ø if and only if & is invalid.
Proof. For the case of BPE, we prove each direction as follows.
If (tt)) = Ø then e is invalid: Since (ttt) G, we know that there exist sequence such that encode(x) = th. This means there is also no string that satisfy encode(s)f = ef. As such, for ) we do not have encode(decodee(f) the result.
tf. which proves
If t is invalid then (t") = Ø: Let Let decode(t(). it is sufficient to consider two string 81 and 82 that both have prefix æf- Furthermore, we assume the first tokens of 81 covers exactly x², ie. 2/ dccode(t?) and similarly, the first tokens of covers exactly x", i.c. xf decode(t")) Then:
Proving that invalid et leads to x(th)
$1,
Re-running the BPE algorithm for sı and 82 in parallel, we know that there will be no merge between any suffix of xf and the rest of strings, i.c. s1 \oT and s2 \rT due to the condition above (See Algorithm line 6).
Furthermore, for $1, any time merge happens within xf then the same merge must also happen within 2t for 82 and vice versa.
14

---

Published as a conference paper at ICLR 2025
As the result, we have ti = E and they must be equal to encode(x?).
For the case of MPE, the proof is similar:
If ((t) Ø then if invalid: Since x(+)) = Ø, similar to the case of BPE, we know that there exist no string such that encode s)f tf. As such, for decode(tf), do not have encode( decode(tf)) = tf. which proves the result.
If of is invalid then (14) Ø: = = ) we consider two string 81 and 82 that both have prefix xt. Furthermore, assume the first i tokens of 81 covers exactly zi, i.c. z = decode(fi) and similarly, the first tokens of $2 covers exactly 27, i.c. "i d Since the MPE tokenizer will greedily looking for the longest token, hence one of the the encodings must not follow MPE encoding rule (contradiction).
This concludes the proof.
A.5 TOKENIZATION BIAS UNDER STOCHASTIC TOKENIZERS
Another class of tokenizers is non-deterministic, such as BPE Dropout (Provilkov al., 2020), to address model's weakness against text fragmentation by randomly omitting tokens before text pro- cessing, theoretically training the model in multiple vocabularies. Although intended enhance robustness, our analysis suggests that tokenization bias still exists despite less obvious. It is partially mitigated, nevertheless, since the model needs minimize loss across varied vocabulary sets. The BTR lemma (Lemma 1) holds, requiring consideration of all valid encodings under this variability. In practice, given the substantial size of the vocabulary. BPE-dropout expected be robust to tokenization bias, i.c. assigning non-zero probabilities to invalid encodings. Yet, it is not commonly employed in training large-scale L.LMs because the randomized tokenization introduces a compu- tational bottleneck, which slows down the training process. Also, it may require greater model capacity to handle the increased complexity.
We demonstrate the tokenization bias in BPE-droupt in the following experiment. Here, we use the 1st order Markov chain example as in Figure where (a, 3) = (0.4, 0.3). We train a LLM with BPE dropout where sequence can be tokenized either with the vocabulary V1 { ("A", "B" "AA" or 1/2 = ("A", "B"} } with equal probability. Consider the following input tokens (separated by and their next-token probabilities:
"I A I and next token probabilities { "A" 0.43, "B" 0.57, "AA" 10-5), 5]: tokenization bias happens according to Definition 2 but the probability does not go to 0.0 as the cross entropy loss distributed between the two vocabularies.
"I BB A IAIAI l" and next token probabilities ("A" 0.59, "3" 0.41, "AA" 10-33: which approximately equal to the original byte-level probabilities since the LLM detects that the only possible vocabulary that produces these tokens 1/2 = { (AA", "B"}.
"IB AA |AI 1 and next token probabilities {AA" 10-1 "g" 0.99, "AA" 10-53: tok- enization bias occurs, i.c. the LM only outputs token "B". Since "AA" only occurs in the vocabulary V { ("A", "B" "AA"), ). the LLM detects the tokenization pattern and infer that the sequence must be tokenized with this vocabulary.
Finally, for the first case "BA", can recover the exact probability by using the BTR lemma. In this case, its cover encoding and associated probabilities are t = BB All 12 = |B|AA| and P(tz) 0.104 and P(tz) 0.0415. For the string "BAA", the first cover encoding is tz. which is already computed and the other one is (3 BB A A and P(la = 0.0443). Using factorization, obtain a 0.405, which is approximately equal the the original value of 0.4.
A.6 ON PREDICTIVE DISTRIBUTION OF LANGUAGE MODELS
In practice, LMs trained with BPE/MPE often do not strictly follow Proposition 1 due to softmax activations. In this section, we show that given any tokenized LM, we can force its output probabil- ities to obey Proposition 1, without any loss in terms of perplexity score on the token domain. In
15

---

Published as a conference paper at ICLR 2025
other words, turn tokenized language model that does not follow Proposition 1 to the one that does while guaranteeing that the new model will always result in a lower token-level perplexity score.
We first introduce Proposition 2. In this proposition, we are given a target discrete probability distri- bution p where we know some of the values will not happen, says $* Assume that have another distribution & that approximates p. then we can produce another distribution q" that is closer to p in terms of KL divergence by setting corresponding probabilities of in & 0.0 and renormalize it.
Proposition 2. Given a discrete distribution p = {p1. Pa.,.,,.,, and = {41, 92. Ina J with % > 0.0 for all Let + {i Zip; 0.0} and 4* S &, we define q" -4 ...... om I where q.- = f.r i E Φ", and 9j (5/(i igg- q1). Then we have:
(xl(Plla)) S (Kl(p)
(9)
which implies that qº is closer to than q. We refer to the process of producing q" as truncate- renormalization (TR).
Proof. Let Z (EiE0 4) is the normalizing factor in q² Note that Z s 1 and as such log(Z) s 0.
Then:
(pl(") = Σ Pt log
Pi 9i
(10)
Σ
ps log
Pt
use 0 log 0 = 0.0
(11)
0,¹
i
Σ ps log
Ps
(12)
qi/Z
Σ Pa log
Pi
())(Z)
(13)
9:
Lig'
$ Σ ps log
Pi
(pl()
(14)
which completes the proof.
Applying to our scenario, for any autoregressive LM P1 (tx+1|tf) that does not follow Proposition (due to the softmax activations), we can perform the TR process (since we know which encoding is invalid) to obtain new LM (2 I(f),, which is guaranteed to better approximate the ground-truth model P(tx+1lt() Thus, we are guaranteed that the token-level perplexity score of 1 1 is always lower than or equal to P1 (t) Finally, in practice, observe that the conditional Pi (1x+11// (14) for invalid 42+1 is significantly smaller than the valid tokens.
A.7 THE MARKOV CHAIN EXAMPLE
We provide a detail computation of the Markov chain example in the main paper. Recall that in the original chain (in the character domain), we have the following:
P(22 = "A" [1 = "A") = 1 - a
(15)
P(r- "B" [21 "x")
(16)
P(#z = "A" [x1 = "B") =
(17)
P(x2 "B"(21 "B") =1 3
(18)
We also assume the initial probability domain, let first compute P(tz = "A" |1 = "AA") where we have:
{y, 1 7 for "A" and "B" respectively. In the token
P(t2 = "A" 4, = "AA") = P(r5 = "ABA" |o² = "AA") + P(x "ABB"|a = "AA")
(19)
= =P(13 = "AB" | = "AA")
(00)
a0 -a),
(21)
16

---

Published as a conference paper at ICLR 2025
where in the first equality, do not include the case 23 "AAA" and z encode( "AAA")1 ) = "AA" and encode( "AAB")) = "AA", which are not the token "A" that we interested in. For other tokens when = "B" the computation follows the same arguments.
"AAB" since
Finally, for the case t = "A", we note that it implies the second token must be "B" since any "A" after the first "A" must be tokenized into "AA" (invalid tokens). Hence, we have P(t2 = "e" "A")= = 1.0. Finally, in this specific Markov chain, since order of the Markov chain in the character domain is 1, we do not need to consider the higher order of the Markov chain in the token domain.
Higher-Order Markov Chain Experiment Setup. We validate the estimated byte-level probabil- ities of the BTR Lemma (Lemma 1) using the Markov chain's transition probabilities ground truth. Specifically, we simulate the data generating process as a 3rd order Markov chain with two states A "AA", "B"), ]. where we randomly construct the transition matrix and the vocabulary V =" ; "ø", "B.A", "BA-A", "B-BAA", "A-A", "BA-BA", "B.B"). Here, the order within V is the merging order for the BPE encoding process and the *." separates the merging tokens. We then train a LM model using GPT-2 architecture with 6 hidden layers on the synthetically generated data. Since the model is agnostic to the Markov chain order, we average the probability from 100 runs on different context length while fixing the last 3 bytes.
A.8 NEXT-BYTE SAMPLING ALGORITHM
Algorithm 3 shows the next-byte algorithm in Section 4.2. Note that for ( we do not need to iterate over every time since the mapping from tokens to their prefix byte can be precomputed (line 30-33).
B NOTEWORTHY IMPLEMENTATION CONSIDERATIONS
Theoretically, we do not have to predict into utf-8 byte space. We could predict into the largest set of tokens A that is contained in the vocabularies of all members of model ensemble: max |||||| s.t. A C V; for all i. This can have certain advantages, the primary one being that generation would be faster: for example imagine average token has four bytes. Our method now needs to predict four times instead of one to generate the same expected amount of text. In this context, note that symbol based languages such as Chinese characters bytes. Hence our method can be performance optimized by specializing the alphabet. Please note that our choice of alphabet does not change the statistical properties of the model, hence we would not expect accuracy differences due alphabet choice. However, the primary reason for us to choose the byte alphabet regardless was the ease of use for model ensemble: To run any experiment we need to map tokens probabilities to universal alphabet, that is the easiest defining the alphabet as 255 bytes and the necessary control tokens.
often based on multiple
C ABLATION: BEAM SEARCH
Each token is made of 6.6 byte on average. Thus, a tokenized model might have more foresight compared a byte-level one when predicting one step at a time. Hence, even though, beam-search has not led to improvements in tokenized models (Holtzman al., 2020; Stahlberg & Byrne, 2019; Koehn & Knowles, 2017), this might be different for byte- level models.
Beam width
PSM
SPM
65.7
63.9
66.8
65.9
67.7
66.8
We repeat the FIM experiments with beam-width 1, 2 and 4, shown in Table 3. Consistently, we see an about 1% improvement for each prompt- ing style and each beam-width increase. However, beam-search notably increases the memory footprint of any LLM because modern transformer based models need to store the KV-cache of each beam for efficient gen- eration. Since the KV-cache makes about 2/3 of the overall memory consumption beam search is memory intense operation.
Table Performance in- creases for the next-byte prediction on our FIM- task when beam search is applied.
17

---

Published as a conference paper at ICLR 2025
Algorithm Compute (a(. which is a conditional distribution of all bytes A. Cu+1 (a) and (a) also contain the encoding probability P(t) for each encoding they contain.
procedure COMPUTH(**) cover_dicttee
Nonc)
2:
if cover d'eover_ddctee (x) None:
3:
P( cover cover_dictxxf)) = CESTRACT.COVERRCC.
4:
# Get the set (a) (See Section 4.2) for all a E A
5:
(Cn+1(a)), Cn+1 (a(A)) = REGROUP wNCoDiNGs(coverr.iittt Get the set Cn+1 (a) (See Section 4.2) for all a E E T= encode(rT); Query P(() from cover ()"))
6:
7:
8:
(an+1(11),... Cn+1(a)A))) =EWD WWW.NNEEEECCDDDNSS..PPP.. P(t)) # Merge cover dictionaries.
9:
10:
for a E A do
Ent1 = cover,dict(2f (n+i (++1(())
P(x)+1) Liecover dictl=] P(t)
14:
end for
15: Obtain Pa((22)) by renormalizing P(a
16: return Pa(-1x7), [cover dict(x?++) for #n+1 E A)
17:
end procedure
18:
19: procedure REGROUP CEA.OOPPEENODDNNSscvee..........
20: for E, P(t) E cover_dict(z)) do
21: byte = decode(t)
22:
(byt(byte)(E Ptt)
end for
24: return (01+ ... C
end procedure
26:
27:
procedure ADD_NEW LEN.DDEIEC,, P(tf))
28:
Compute P(t++1 t t)t for all E V # Run I model inference for all
29: Compute P(1 P(4-1 1115) P(1T) for all E V # Broadcasting for all I.
30:
for L do
31:
byte decode(t4+1)
(byteb)te) P
33:
end for
34: return ( (nt1(()1))
35: end procedure
D FIM CODE GENERATION EXAMPLES
Here, we show three examples from the random span FIM benchmark from Bavarian et al. (2022) that we evaluate on in Figure 6. Our greedy byte-level generations significantly improve upon the greedy token-level generations in the SPM (suffix-pretf -suffix-prefi-mmiddee mode with Code ama-7b be- cause the prompt ends with the "prefix" portion of the code and the generation starts token boundary. Each figure visualizes an example from the benchmark with the prefix and suffix at the beginning and separated by MILL--M) indicating the portion for the LLM generate. Then, show the generations from the token and byte-level models in SPM mode along with token healing baseline. They illustrate exactly where tokenization issues arise when generating and show how the byte-level predictions correct them.
18

---

Published as a conference paper at ICLR 2025
Code generation example with CodeLlama- This one is interesting because of the typo in the variable "del immtte" in the dataset and the prefix ends with "del iml. The mis- spelled "del meelimete" is tokenized as two tokens: "del imeter" while the correctly spelled "del iemitiii"rrr is tokenized as single token. This makes the 1) token-level prediction incorrectly generate "ter" as the continuation because "del I imter" tokenized as three tokens "del im ter", which has a token boundary at the end of the prefix, 2) token-healed predictions incorrectly generate "iter" because at the token-level, "delinee milliierr"" more likely, and 3) byte-level pre- dictions correctly generate "eter" because the probability at the byte-level correctly marginalizes out the byte-level probability despite the context and many possible tokenizations.
Listing 1:
from typing import List
def intersperse (numbers: List [int], delimeter: int) -> List[int]] [int]: Insert number 'del imeter! between every two consecutive elements of input 1ist "numbers'
>>> intersperse (1l, 4)
11
>>> intersperse (12, 2, 31, 4)
[1, 4, 2, 4, 31
if not numbers: return []
result []
for n in numbers [: [1-1]:
gesult.appendi
Result.apeent (delim (FILL ME)) mbers [-1])
return result
token predictions (did not pass X):
ter)
assuld.apeendiin
token predictions with token healing (did not pass X)
iter
result.apper (nu
byte predictions (passed V) ster) result t. append (nv
Listing 2: Code generation example with CodeLl ama-7b. 7b. This one is interesting because of the tokenization of "col latz" and the prefix starting with "col 1 la". "col latz" is tokenized two tokens "coll atz". This makes the 1) token-level prediction incorrectly generate "zt" as the continuation because "coll lazt" is tokenized three tokens "col la zt", which has token boundary at the end of the prefix, 2) token-healed predictions incorrectly generate "pse" because the token-level after backing up, "col lapse" (a single token) is more likely, and 3) byte-level predictions correctly generate "tz" because the probability at the byte-level correctly marginalizes out the byte-level probability despite the context and many possible tokenizations.
RandomSpanInff htg.://aaaaaaaiiiaoaaa////a///// def *** cod__cclltt2())
Given a positive integer n, return a sorted list that has the odd numbers in collatz sequence.
The Collatz conjecture is conjecture in mathematics that concerns sequence defined
as follows: start with any positive integer n. Then each term is obtained from the
19

---

Published as a conference paper at ICLR 2025
previous term follows: if the previous term is even, the next term is one half of the previous term. If the previous term is odd, the next term is times the previous
term plus 1. The conjecture is that no matter what value of n, the sequence will always reach 1.
Note:
1. (ollatz(2) is [1].
2. returned list sorted in increasing order.
For example:
collatz (5) returns II, 5] The collatz sequence for is 15, 16, 8, 4, 2, 11, so the odd numbers are only 1, and 5.
n82==0: ood_ctl = []
else:
odd colla (FILL-ME)
if n$2 == 1:
odd collatz append (int (n)
return serted codd_collate)
token predictions (did not pass X)
zt [n]
while 1= 1:
if n$2 0: n n/2
else:
n 3an +
token predictions with token healing (did not pass pse ||
odd collatz = [n] while !- 1:
if n$2 0:
n n/2
else:
n 3en +
byte predictions (passed V) t2 [n]
while n != 1:
if n&2 =- 0:
n/2
else:
n 3+n +
Listing 3: Code generation example with CodeLlama-ie 7b. This one is interesting because of the tokenization "pal inddomee" and the prefix starting with "palindr"" "palindrome" is tokenized as three tokens "pal ind rome". This makes the 1) token-level prediction incorrectly generate "one" as continuation because "pal indroee" is tokenized as four tokens "pal ind one", which has token boundary at the end of the prefix, 2) token-healed predictions incorrectly generate "eome" and results in the three-token chunk "pal indre ome" because the token healing did not successfully search backward enough, and 3) byte-level predictions correctly generate "ome" " because the probability at the byte-level correctly marginalizes out the byte-level probability despite the context and many possible tokenizations.
20

---

Published as a conference paper at ICLR 2025
Bendos/perdddiiiih///aaaaaaaaaaa def oven_odd__allndree (
a**
iven a positive integer n, return tuple that has the number of even + and odd
integer palindromes that fall within the range (1, n), inclusive.
Example 1:
Input:
Output: (1, 2)
Explanation:
Integer palindreme are 1, 2, one of them is even, and two 4 them are odd.
Example 2:
Input: 12
Output: (4, 6)
Explanation:
Integer palindrome are 1, 2, 3, 4, 5, 6, 7, 9, 11. four of them are even, and of them are odd.
Note:
1. <= <= 10"3
2. returned tuple has the number of and odd integer palindromes respectively.
def is palindr (FILL-VE) odd palindrome_coort
for i in range (1, n+1]:
if 1&2 -- and is_palindreme (i)
odd_palindrome__r
elif i&2 0 and is_palindrome (1):
even www.ppaaallleecooem cocndrrme_cccutttto +=
return lare__palindrrmm_cout,,, edd edd_paliindrome_omme
token predictions (did not pass X);
one (n)
return str (n) = str [::-1]
def is_palindromes (n)
return is_palindrone indrone (n) and n >-
even_ www.ppaaaldoecccooto count
token predictions with token healing (did not pass X) eome (n)
return str (n) (n) [::-1]
even_pallidrrmm_ccomt 0
byte predictions (passed V):
ome (n)
return str (n) str (n) [::=1]
even_ealindrome_cout
21

---

Published as a conference paper at ICLR 2025
E ANALYSIS OF TOKEN ALIGNMENT
Recently, Athiwaratkun et al. (2024) also proposed a similar method to mitigate the tokenization bias issue. In this method, they start regenerating the last B tokens in the prompt by restricting the next-token to be either prefix of the prompt's 's remaining string or cover it, i.c. the remaining string the prefix of the generated token. Although this appears overlap with our Corollary the sampling procedure is biased and can produce invalid encodings due to the greedy masking process.
Consider the following example where we use the following vocabulary {< (<>>,<>) <1>, <a>, <> < <aa>>} with MPE tokenizer. For a prompt string aa" which tokenized as <.a>, token alignment will regenerate from the beginning and force the generated tokens to match the template "_a". This is problematic when the first token generated is <_>. Given this token, tokenization bias occurs and the second token must not be <a> since <_a> whole token. On the other hand, according to token alignment, the only possible next token after <_> is <a> but <_><a> is an invalid encoding. The correct way to align is to by rejection sampling without greedy masking. We can also our method by generating bytes until seeing white space, then switch to token level generation. In this case, the prompt should exclude the last whitespace, and the first generated token must start with whitespace.
22


Reviews:
[{"review_id": "qsjymS7yaz", "reviewer": "Reviewer_oJBc", "summary": "This paper reveals a fundamental issue in language models regarding tokenization bias - where tokenized and byte-level models, despite being statistically equivalent, produce different predictive distributions. The authors introduce the Byte-Token Representation Lemma, providing a framework to convert tokenized language models into statistically equivalent token-free ones without additional training. They demonstrate practical applications in fill-in-the-middle tasks and model ensembles, achieving significant improvements: 18% on FIM coding benchmarks and up to 3.7% on ensemble tasks. The paper provides both theoretical foundations and practical implementations through efficient algorithms for cover encoding search and next-byte sampling.", "questions": "See weakness above. In addition, \n\n1. Do authors plan to open-source the implementation?\n\n2. There is also a line of work similar to token healing and seems working well in both code and text. Could the authors study it and see whether the token alignment method could mitigate the issue especially in single-model completion tasks? \nToken Alignment via Character Matching for Subword Completion https://aclanthology.org/2024.findings-acl.929.pdf", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors attempted to address a critical problem on tokenization for LLMs. They are the first to introduce tokenization bias and its effects on model behavior. They present a theory of it and introeduced efficient implementation of the algorithm.\n\nThe authors also studied the practical impact of the proposed solution through both code generation task (FIM, speficially) and model emsambles. Results indicate that this training-free approach is working well.", "weaknesses": "While the current results are great, it'd be better if authors can also cover tasks other than FIM that suffer from this issue, e.g. complete a story in natural language or generic code completion task that doesn't require FIM.\n\nThe authors discussed computational overhead but doesn't thoroughly analyze the latency impact especially in a practical setting. It'd be better if authors can study these as part of the experiments authors conducted.\n\nThe interaction between the proposed byte-level prediction method and popular sampling techniques (like  top-p, top-k) have not been explored enough, especially in the ensemble context.", "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": "2F6PxspbbK", "reviewer": "Reviewer_X7br", "summary": "This paper investigates the impact of tokenization on the performance of language models, particularly highlighting a phenomenon called \"tokenization bias.\" This bias comes from the discrepancies between the predictive distributions of tokenized LMs and their statistically equivalent byte-level distribution when predicting the next byte or token. In this paper, they introduce the Byte-Token Representation Lemma (BTR Lemma) to map between the token and byte domain, which allows the computation of exact byte-level probabilities without requiring extra modification of the model. This method identifies \"cover encodings\" for a given byte string which are all possible valid tokenizations of a string that \"optimally\" contain the string in the prompt. Experiments on FIM code completion task and model ensemble task show that the proposed method improves model performance.", "questions": "* How is the proposed method compatible with other tokenization algorithms besides BPE and MPE?\n* What do the right two sub-figures mean in Figure 6?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* This paper defines the tokenization bias phenomenon, which could cause performance issues in practical scenarios. \n* They evaluated the proposed method on FIM code completion task and mode ensemble task. \n* The proposed byte-level prediction method considers both the accuracy and efficiency in recovering the unbiased byte-level distribution.", "weaknesses": "* This method is very similar to the ACL 2024 paper 'Token Alignment via Character Matching for Subword Completion' which addresses the same issue and proposes more evaluation scenarios. However, in this paper, they didn’t compare with the token alignment method. \n\n* Based on the results shown in Figure 6, the improvement of the proposed method on the FIM evaluation tasks in sampling settings (pass@10) over the token-level with token healing method is very minor. For example, from 84.0 to 84.1. Why is that? \n\n* The evaluation scenarios are limited. Only two types of tasks are covered. How’s the performance of the method on general completion tasks without the FIM setting? Does the tokenization bias also have an impact on natural language completion tasks?", "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": "r8WKfa2uaH", "reviewer": "Reviewer_KAHr", "summary": "This paper provides a thorough investigation into the phenomenon of tokenization bias in language models, proposing a byte-level prediction method to mitigate this bias. The approach has promising implications, especially for tasks like fill-in-the-middle (FIM) in coding and for model ensembling. The idea of combining language models with distinct tokenizations at the logit level recalls older ensemble methods, commonly used before tokenization became mainstream in modern LLMs. The proposed method, underpinned by the Byte-Token Representation Lemma and efficient sampling algorithms, allows for effective ensemble models by bypassing tokenization restrictions, facilitating seamless integration across diverse language models.", "questions": "I am curious what do authors think about the generalizability of their methods to non-deterministic tokenization or in applications that involve mixed token vocabularies ? Could some experimental results be shown to further strengthen the paper ? \n\nHow do authors explain the not-so-strong gains with ensebling (Table 1 and Table 2). It was not clear how the models are being ensembled together? I would have also liked to see other combination strategies as a baseline e.g. consensus voting or ranking over diverse samples from different LMs. Are these experimental results available ? \n\nIn order to truly appreciate the need for this research, its important to know just how much diverseity there exists in tokenization vocabulary across different LLMs today. To that end, I would like to see some sort of distribution characterizing the popularity of tokenization and distribution of vocabulary sizes across various LLMs. If the world is already coverging to one tokenization and the vocabulary of tokens homogenizes over time, then what practical advantages does this paper bring ? We should debate whether or not this is true and I would like to see authors providing their rebuttal.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "What I really liked about this paper is that it very systematically investigates the phenomenon of tokenization bias. It develops a byte level prediction method and overcomes the bias. The applicability of this method and the findings in the paper have implications in areas such as coding where fill in the middle is crucial as well as in model ensembling. The idea of combining ensembles of foundation models at the logit layer is very appealing. Back in the day when there were no tokens and LMs were being built on whole words, ensembling using to be the norm in any practical LM based applications, such as speech recognition. With varying tokenization powering different LLMs today, the ability to freely combine any LLM with each other became restrictive. This paper proposes byte level efficient sampling algorithms and in conjuction with the byte-token representation lemma and the associated theoretical foundation, now allows the community to confidently combine predictions from any LLMs. Tokenization allows the LMs to overcome closed vocabulary limitation and from my perspective, this paper further allows us to overcome distinct vocabulary challenges associated with model ensembling.", "weaknesses": "While the results are promising for fill in the middle (in coding) tasks, I would have liked to see experimentation on other tasks to ascertain this method's generalizability to a wider variety of tasks, espically those that require context senstitive token predictions. Computer use, a new usecase demonstrated by companies such as Anthropic, could be a good use case that the authors could consider as an example. \n\nAn area that authors could delve further into is more analysis on the tokenization bias in multi step or long context tasks. \n\nIn order to truly appreciate the need for this research, its important to know just how much diversity there exists in tokenization vocabulary across different LLMs today.", "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": "mKiEATiZZv", "reviewer": "Reviewer_v6Xm", "summary": "Tokenization is a common pre-processing step, which shortens input sequences by mapping multiple bytes to discrete tokens. \nPrior work finds: Even for unlimited data and compute, tokenized models can achieve better cross-entropy loss vs. untokenized models\nOne hypothesis for why tokenization helps is that it allows models to handle longer contexts at less compute\nMain problem: there are certain combinations that cannot be represented in token space, limiting the model’s abilities. This is harmful esp. for prompts that end mid-token.\nApproach: this work presents a way to predict when tokenization is getting in the way and converts tokenized LMs into statistically equivalent byte-level models", "questions": "In the caption for Figure 2, should the probability of sampling “A” on the LHS be $(1 - \\alpha)$? It states the probability is $\\alpha$.\n\nI would be willing to change my opinion based on the responses to the weaknesses!", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The characterization of the tokenization bias phenomenon, with examples / and the synthetic example with a 3rd order Markov chain, is very interesting and useful to the community\n- The paper is well-written and studies an important problem", "weaknesses": "- The code infilling setting is an interesting example of where this work could be useful. However, it is not clear why the prefix would stop in the middle of a token/word or why new tokens would arise at inference time. Why are the <PRE>, <MID>, and <SUF> tokens needed? Why is the study restricted to two prompting formats/are others possible? Since tokenization schemes are lossless, it seems like any prefix should be representable with the set of available tokens at training time. Further explanation of the evaluation setting and why it is realistic would be helpful.\n- Several prior methods can ensemble the predictions from models that do not share a vocabulary, or ensemble multiple predictions from a single model (https://arxiv.org/abs/2203.11171, https://arxiv.org/abs/2210.02441, https://arxiv.org/abs/2307.11031). It is not clear whether the ensembling method proposed in this paper would outperform these methods . The motivation that byte-representations help ensembling is not fully examined due to the lack of these comparisons.\n- It would be useful to provide decoding efficiency metrics corresponding to each decoding approach in Figure 6 since efficiency is a motivation in Section 4.", "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)