Exact Byte-Level Probabilities from Tokenized Language Models for FIM-Tasks and Model Ensembles

## Abstract

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 an approximately 18% improvement in FIM coding benchmarks, 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.

## 1 Introduction

Transformers form the backbone of all widely-used state-of-the-art language models (LMs) such as GPTs (Brown et al., ), Llama (Touvron et al., ), ans Mistral (Jiang et al., ). A common pre-processing step in these models is tokenization, a method that shortens the input sequence by mapping multiple bytes, i.e. characters into discrete tokens, i.e. words or subwords, from a fixed vocabulary (^1^11We use the terms “characters” and “bytes” interchangeably to refer the basic elements that builds up the tokenization vocabulary. This subset is somewhat flexible. Precision is only important in the experiment section where we define the subset to be all utf-8 bytes.).
Efforts to bypass tokenization have shown limited empirical success (Yu et al., ; Limisiewicz et al., ), 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 is due to the reduction of input tokens, allowing models to handle longer contexts at less compute (Zouhar et al., ; Goldman et al., ).
Recent work by Rajaraman et al. () provides an additional explanation: Even for unlimited data and compute
(^2^22And assuming the data source can be approximated as a $k^{th}$ order Markov chain.), tokenized models can achieve better cross-entropy loss than untokenized ones, resulting in superior performance.

To contribute to the understanding of the impact of tokenization, we demonstrate that for any tokenized LM, there exists a statistically equivalent byte-level process. Despite their statistical equivalence in terms of training loss, we find a surprising discrepancy in their predictive behaviors—particularly in next-token and next-byte predictions, 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-Token Representation Lemma (Section 4.1).
The lemma enables both byte-level predictions and an algorithmic correction of tokenization bias in any trained LM without the need for additional training or optimization, allowing us to sample bias-free next-bytes from any tokenized LM.

Figure: Figure 1: Left: Tokenized LMs can experience tokenization bias when prompts end mid-token, as in this code completion example. This means the correct solution a has zero probability of being chosen. Our method avoids this problem and predicts the correct token while using the same model. Right: We map next-token predictions of arbitrary tokenized LMs to statistically equivalent next-byte predictions (see Section 4.1). This enables any model ensemble strategy, such as averaging or mixture of experts.
Refer to caption: x1.png

Because our findings show that tokenization introduces an irreducible gap between the token and byte domains by preventing certain token combinations, limiting the model’s ability to sample specific tokens, we investigate this issue in fill-in-the-middle (FIM) tasks. Tokenization bias is particularly harmful in fill-in-the-middle (FIM) tasks when a prompt ends mid token. Tokenized language models struggle to predict the correct completion (Dagan et al., ). Our theory predicts this phenomenon precisely, and the failure example shown in Figure 1 (Left) can be reproduced with any open-weight model to date. In our experiments, we demonstrate that our next-byte prediction method outperforms tokenized models with the same cross-entropy by 18%, and even surpasses a specialized fix, token healing (Dagan et al., ; Roziere et al., ), by 1%.

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 do not share a vocabulary. However, by mapping 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 advantageous because model ensembles are generally more accurate and robust than any individual member (Hastie et al., ). We also confirm this experimentally: models that are ensembled using our byte-level predictions outperform individual models in many cases.

In summary, the key contributions of this work are:

- 1.
We convert tokenized LMs into statistically equivalent token-free models, and demonstrate that their predictive distributions differ. We define this discrepancy as tokenization bias.
- 2.
We introduce a 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 an O(1) computational cost in terms of model runs.
- 3.
We present strong empirical evaluations on an FIM benchmark (18% improvement) and model ensemble tasks (up to 3.7% improvement), further demonstrating the effectiveness of our approach.

## 2 Notations and Setup

### 2.1 String and Byte-Level Language Models

We denote the alphabet set as $\mathcal{A}$ and its element character, or byte, as $x$. By default and consistent with real-world data, unless otherwise stated, we include the end of string <EOS> byte in $\mathcal{A}$. For any (finite) string $s$, we denote its substring from location $i$ to $j$ as $x^{j}_{i}\vcentcolon={x_{i}x_{i+1}..x_{j}}$. We view any byte-level LM as a discrete stochastic process that defines the autoregressive probability $P(x_{n+1}|x^{n}_{1})$ for all $n$. This defines an infinite (stochastic) sequence $\mathbf{x}=x_{1}x_{2}...$ where $\mathbf{x}\in\mathcal{X}$. With the existence of <EOS>, we have $P(x_{n+1}|x^{n}_{1})=1.0$ for $x_{n+1}=x_{n}=$<EOS> and $P(x_{n+1}=\verb!<EOS>!|x^{n}_{1})\neq 0.0$ for any $x^{n}_{1}$. Effectively, $\mathbf{x}$ has finite length and the set $\mathcal{X}$ is countably infinite. We refer $\mathbf{x}$ as a byte sequence instead of a string, which has a finite length and does not necessarily end with <EOS>.

Given $x^{n}_{1}$, the function $\mathrm{prefix}(.)$ returns all possible prefixes of $x^{n}_{1}$, i.e. $\mathrm{prefix}(x^{n}_{1})=\{x^{1}_{1},x^{2}_{1},x^{3}_{1},...,x^{n}_{1}\}$. We denote the concatenation operation as $\mathrm{concat}(.)$, i.e. $\mathrm{concat}(x^{n_{1}}_{1},y^{n_{2}}_{1})=x_{1}...x_{n_{1}}y_{1}...y_{n_{2}}$. We define $\mathcal{X}(x^{n}_{1})$ as the set of all byte sequence $\mathbf{x}$ with prefix $x^{n}_{1}$, i.e.

$$ $\mathcal{X}(x^{n}_{1})=\{\mathbf{x}|x^{n}_{1}\in\mathrm{prefix}(\mathbf{x})\},$ $$

which corresponds to the byte-level probability of obtaining a sequence with prefix $x^{n}_{1}$, or $P(x^{n}_{1})$.

### 2.2 Tokenized Language Models

We consider two commonly used tokenization algorithms, namely Byte-Pair Encoding (BPE) (see Algorithm 2 in Appendix A.4) and Maximum Prefix Encoding (MPE).
Tokens are elements within a vocabulary $\mathcal{V}$, where $\mathcal{A}\subseteq\mathcal{V}$, an individual token is denoted as $t\in\mathcal{V}$. We also assume <EOS> is not a part of any token but itself. An encoding of length $k$ of a string $x^{n}_{1}$ is $t^{k}_{1}=\mathrm{encode}(x^{n}_{1})$. Conversely, a decoding of $t^{k}_{1}$ is a string denoted as $x_{1}^{n}=\mathrm{decode}(t^{k}_{1})$. Encodings with an unspecified number of tokens are denoted as $\vec{t}$. Note that BPE and MPE are deterministic, i.e. each string $s$ and sequence $\mathbf{x}$ correspond to a unique encoding (lossless compression). Furthermore, we define $\mathcal{X}(t^{k}_{1})$ as a set consisting of all sequences whose encodings start with $t^{k}_{1}$, i.e.

$$ $\mathcal{X}(t^{k}_{1})=\{\mathbf{x}|t^{k}_{1}=\mathrm{encode}(\mathbf{x})^{k}_ {1}\},$ $$

which corresponds to the token-level probability $P(t^{k}_{1})$, i.e the probability of obtaining a sequence whose encoding starts with $t^{k}_{1}$. We also view any tokenized LM as an autoregressive process that defines $P(t_{k+1}|t^{k}_{1})$ and refer to an infinite token sequence as $\mathbf{t}=t_{1}t_{2}...$ and $\mathbf{t}\in\mathcal{T}$. Similar as the byte-level process, with the existence of <EOS>, $\mathbf{t}$ is effectively finite and $\mathcal{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, we show that byte-level LMs and their induced tokenized LMs are statistically equivalent.

###### Definition 1 .

(Statistical Equivalence)
For a countably infinite set $\mathcal{X}$, the byte-level data generating processes $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ are statistically equivalent if and only if:

$$ $P_{\mathcal{G}_{1}}(\mathbf{x})=P_{\mathcal{G}_{2}}(\mathbf{x})\text{ for all }\mathbf{x}\in\mathcal{X},$ $$

i.e. chances of sampling sequence $\mathbf{x}$ are identical for processes $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$, denoted by the subscripts.

We consider the following two stochastic processes:

- •
$\mathcal{G}_{1}:$ the ground truth byte-level language models $P(x_{n+1}|x^{n}_{1})$.
- •
$\mathcal{G}_{2}:$ consists of the tokenized model $P(t_{k+1}|t^{k}_{1})$ induced from the process $\mathcal{G}_{1}$ and tokenization. The process $\mathcal{G}_{2}$ generates sequence $\mathbf{x}$ by autoregressively sampling new $t_{k+1}$ and maps $t_{k+1}$ to its byte-level representation using the $\mathrm{decode}(.)$ function.

Since the mapping defined by the tokenizer for the sequence $\mathbf{x}$ and its encoding $\mathbf{t}=\mathrm{encode}(\mathbf{x})$ is bijective, we have $P(\mathbf{t})=P(\mathbf{x})$, leading to two processes being statistically equivalent. This implies that it is possible to convert any tokenized LM to its statistically equivalent byte-level counterpart.

###### Definition 1 .

### 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.

###### Definition 2 .

(Tokenization Bias) Let the input prompt $x^{n}_{1}$ have the corresponding encoding $t^{k}_{1}{=}\mathrm{encode}(x^{n}_{1})$. The tokenization bias occurs for this prompt when:

$$ $P(x_{n+1}|x^{n}_{1})\neq P(x_{n+1}|t^{k}_{1}),$ (1) $$

where $P(x_{n+1}|t^{k}_{1})=\sum_{t\in\mathcal{E}}P(t_{k+1}{=}t|t^{k}_{1})$ and $\mathcal{E}=\{t\in\mathcal{V}|x_{n+1}=\mathrm{decode}(t)_{1}\}$, i.e. the set of tokens whose first byte is $x_{n+1}$.

For example, the probability of the next byte being “c” may be different from the sum of the probabilities of all tokens that start with “c”, which offers a broader perspective compared to the probability of the subsequent token being exactly “c”.

###### Definition 2 .

#### 3.2.1 Tokenization Bias in Markov Chains

Figure: Figure 2: Tokenization bias on a $1^{st}$-order Markov chain. Given the context token $``\texttt{A}"$, the model will never sample the next token as $``\texttt{A}"$, rather than with probability $\alpha$. In practice, this bias occurs when prompts end with tokens that are part of another token, a common issue in the FIM tasks, leading to incorrect completions by the model.

To systematically study tokenization bias, we employ a simplified autoregressive model, representing the data generating process as a Markov chain. As a result, we can derive a closed-form expression for the induced tokenized model and directly observe the tokenization bias phenomenon.

We consider a $1^{\mathrm{st}}$ order Markov chain with two states $\{``\texttt{A}",``\texttt{B}"\}$, shown in Figure 2 (left) where each string is tokenized with either MPE or BPE, which yields the same result. With the vocabulary $\mathcal{V}=\{``\texttt{AA}",``\texttt{A}",``\texttt{B}"\}$, we obtain a new Markov chain whose states and transition matrix are shown in Figure 2 (right). Appendix A.6 provides details on computing the transition matrix. The statistical equivalency between two chains is described in Rajaraman et al. (). First, notice that no tokenization bias occurs when conditioning on $t_{1}{=}``\texttt{AA}"$ or $t_{1}{=}``\texttt{B}"$, e.g.

$$ $P(x_{3}{=}``\texttt{A}"|x^{2}_{1}{=}``\texttt{AA}")=P(t_{2}{=}``\texttt{AA}"|t _{1}{=}``\texttt{AA}")+P(t_{2}{=}``\texttt{A}"|t_{1}{=}``\texttt{AA}")=\alpha$ $$

Figure: Figure 3: Tokenization bias on a $3^{\mathrm{rd}}$ order Markov chain. Our byte-token conversion (bias correction) method in Section 4 accurately recovers $P(x_{n+1}|x^{n}_{1})$ of the original chain.
Refer to caption: x2.png

However, when conditioning on $t_{1}{=}``\texttt{A}"$, tokenization bias emerges, i.e. the probability $P(x_{2}{=}``\texttt{A}"|t_{1}{=}``\texttt{A}"){=}0.0$ is not equal to $P(x_{2}{=}``\texttt{A}"|x_{1}{=}``\texttt{A}")=1{-}\alpha$, i.e. the token-level Markov chain never samples $``\texttt{A}"$ with any prompt ending with token $``\texttt{A}"$. The reason is that whenever two consecutive bytes $``\texttt{A}"$ appear together, the tokenizer immediately merges them into a single token $``\texttt{AA}"$, results in zero probability. Despite being simple, this model portrays the exact phenomenon as the coding example discussed in Figure 1(Left).

Higher-Order Markov Chain. We now show this phenomenon in a more complex, $3^{\mathrm{rd}}$ order Markov chain, but shift from mathematical derivation to an empirical approach to demonstrate its relevance in practice. Furthermore, we leverage 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 a decoder transformer on tokenized data and analyse its next-token probabilities, shown in Figure 3. As we expect, the trained tokenized model exhibits severe bias in its predictions. Nevertheless, when combined with our bias correction technique, we accurately recover the original transition probabilities, demonstrating its potential for generalization to other LMs. We detail the experiment setup in Appendix A.6.

#### 3.2.2 Invalid Encodings

The investigation on the zero probability events observed in our Markov chain example leads us to introduce the definition of invalid encodings, which sets constraints on the probability $P(\vec{t})$ of tokenized LMs.

###### Definition 3 .

(Invalid Encodings) An encoding $\vec{t}$ is invalid if $\mathrm{encode}(\mathrm{decode}(\vec{t})){\neq}\vec{t}$, else it is 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 $\mathcal{V}{=}\{``\texttt{c}",``\texttt{a}",``\texttt{t}",``\texttt{at}",``
\texttt{cat}"\}$, then $\mathrm{encode}(``\texttt{catt}"){=}[``\texttt{cat}",``\texttt{t}"]$. Encodings $[{``\texttt{c}"{,}``\texttt{at}"{,}``\texttt{t}"}]$ and $[{``\texttt{c}"{,}``\texttt{a}"{,}``\texttt{t}"{,}``\texttt{t}"}]$ are invalid.

With this definition, Proposition 1 states that no invalid encodings will exist in the token distribution.

###### Proposition 1 .

$\mathcal{X}(t^{k}_{1})=\varnothing$ if and only if $t^{k}_{1}$ is invalid. As a result, $P(t^{k}_{1})=0.0$. Furthermore, $P(t_{k}|t^{k-1}_{1})=0.0$ if $t^{k-1}_{1}$ is valid, otherwise, it is undefined.

Proof. See Appendix A.4

We note that Proposition 1 indicates the constraints of $P(t^{k}_{1})$ for tokenized LM induced the by byte-level data generating process. For trained LMs, $P(t_{k}|t^{k-1}_{1})$ is not zero for invalid $t^{k}_{1}$ due to softmax activations. Nevertheless, we observe it to be very low compared to the valid $t^{k}_{1}$, as in Figure 3. Finally, we can truncate these invalid probability to zero without any loss in terms of perplexity score, detailed in Appendix A.5.

###### Definition 3 .

###### Proposition 1 .

## 4 Exact Byte-Level Probabilities

### 4.1 Byte-Token Representation Lemma for P ⁢ ( x 1 n ) 𝑃 superscript subscript 𝑥 1 𝑛 P(x_{1}^{n}) italic_P ( italic_x start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_n end_POSTSUPERSCRIPT )

Figure: Figure 4: Left: Representation of $P(x^{n}_{1})$ using tokenized LM with an example of cover encodings and valid/invalid encoding. Right: Illustration of Algorithm 1 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 not shown in the algorithm. We use BPE in this example.
Refer to caption: x3.png

To addresses the tokenization bias, we derive byte-level predictions $P(x_{n+1}|x^{n}_{1})$ from token-level predictions $P(t_{k+1}|t^{k}_{1})$. To this end, we compute $P(x^{n}_{1})$ and begin with the concept of cover encodings of $x^{n}_{1}$. These encodings are valid encodings that “optimally” contain $x^{n}_{1}$, i.e. their last tokens start at locations $i<n$. Results in this section, i.e. Section 4.1, apply for any deterministic tokenizer, not just BPE/ MPE.

###### Definition 4 .

(Cover Encodings) Given a prefix $x^{n}_{1}$, an encoding $t^{k}_{1}$ is said to be covering $x^{n}_{1}$ when all the following conditions satisfied:

- 1.
$t^{k}_{1}$ is valid.
- 2.
$x^{n}_{1}\in\mathrm{prefix}(\mathrm{decode}(t^{k}_{1}))$.
- 3.
$x^{n}_{i}\in t_{k}$ for some $1\leq i\leq n$, i.e. the last token $t_{k}$ covers a part of the string $x^{n}_{1}$.

We denote $\mathrm{cover}(x^{n}_{1})$ to be the set of all cover encodings of $x^{n}_{1}$, with examples in Figure 4 (mid-left).

Following the definition of cover encoding, we establish the BTR Lemma that allows us to exactly compute $P(x^{n}_{1})$ using $P(t_{k+1}|t^{k}_{1})$. The general idea of the BTR Lemma is that any sequence $\mathbf{x}$ that starts with $x^{n}_{1}$ must have one of the cover encodings a prefix tokens of $\mathrm{encode}(\mathbf{x})$.

###### Lemma 1 .

(Byte-Token Representation Lemma)
For a language model $P(t_{k+1}|t^{k}_{1})$, given a prefix $x^{n}_{1}$, the following statements hold:

- 1.
For any distinct $\vec{t}_{i},\vec{t}_{j}\in\mathrm{cover}(x^{n}_{1})$, we have $\mathcal{X}(\vec{t}_{i})\cap\mathcal{X}(\vec{t}_{j}){=}\varnothing$.
- 2.
$\mathcal{X}(x^{n}_{1})=\smashoperator[]{\bigcup_{\vec{t}\in\mathrm{cover}(x^{n
}_{1})}^{}}\mathcal{X}(\vec{t})$.

As a result, $P(x^{n}_{1})$ can be expressed as the marginal probability of all covering tokens of $x^{n}_{1}$

$$ $P(x^{n}_{1})=\sum_{\vec{t}\in\mathrm{cover}(x^{n}_{1})}P(\vec{t}).$ (2) $$

Proof. See Appendix A.2.

###### Remark 1 .

The BTR Lemma provides a general view of tokenization bias. Consider the cover encoding example in Figure 4 (middle-left).
There, given the input string $x^{5}_{1}=``\texttt{yummy}"$, prompting into the models $\mathrm{encode}(x^{5}_{1})=[``\texttt{yum}",``\texttt{my}"]$ will discards the other two possibilities, resulting in a skew distribution over the next-byte, i.e. tokenization bias.

Some scenarios requires conditioning on special tokens, such as when using control/synthetic tokens (e.g., FIM code-infilling). In such cases, we want to compute the byte-level probability conditioned on specific tokens, i.e. $P(x^{n}_{m+1}|t^{k}_{1})$ where $x^{m}_{1}=\mathrm{decode}(t^{k}_{1})$, or equivalently, $P(x^{n}_{1},t^{k}_{1})$. Corollary 1 provides a closed-form expression for this quantity.

###### Corollary 1 .

We can express $P(x^{n}_{1},t^{k}_{1})$
where $\mathrm{decode}(t^{k}_{1})\in\mathrm{prefix}(x^{n}_{1})$ as follows:

$$ $P(x^{n}_{1},t^{k}_{1})=\sum_{\begin{subarray}{c}\vec{t}\in\mathrm{cover}(x^{n} _{1})\\ t^{k}_{1}=\vec{t}^{k}_{1}\end{subarray}}P(\vec{t}),$ (3) $$

i.e., to compute $P(x^{n}_{1},t^{k}_{1})$, we limit the set of cover encodings to those that starts with $t^{k}_{1}$.

Proof. See Appendix A.3.

Finally, to apply Lemma 1, we need to search for all $\vec{t}\in\mathrm{cover}(x^{n}_{1})$, which can be time consuming with naive search. For the tokenizers under consideration, i.e. BPE and MPE, there exists an efficient algorithm by using the properties of invalid encodings (Definition 3). We explain this algorithm in Section 4.1.1.

Figure: Algorithm 1 (Cover Encodings Search). Compute $P(x^{n}_{1})$ and $P(\vec{t})$ for each $\vec{t}{\in}\mathrm{cover}(x^{n}_{1})$.

###### Definition 4 .

###### Lemma 1 .

###### Remark 1 .

###### Corollary 1 .

#### 4.1.1 Cover Encoding Search Algorithm

We present the cover search process in Algorithm 1, which is illustrated in Figure 4 (right). Note that the algorithm also returns $P(\vec{t})$ for $\vec{t}\in\mathrm{cover}(x^{n}_{1})$ which we will use for the sampling later on.
The idea is as 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 $t_{k}$, of a cover encoding $t^{k}_{1}$ is known and it has suffix $x^{n}_{i+1}$, then according to Proposition 1, we must have: $t^{k-1}_{1}{=}\mathrm{encode}(x^{i}_{1})$,
else $t^{k}_{1}$ will be invalid.

As a result, searching from the reverse order, for any suffix $x^{n}_{i+1}$, we can find all tokens that start with $x^{n}_{i+1}$, tokenize $x^{i}_{1}$ and check if their combination is valid or not. The number of model runs is at most $n\ell$, where $\ell$ is length of the longest token in $\mathcal{V}$, in order to compute $P(\vec{t})$. In practice, the actual number of inference runs is much lower since $\mathrm{encode}(x^{i}_{1})$ of the current iterations often contains encodings of the later iterations. Finally, while we can obtain $P(x_{n+1}|x^{n}_{1})$ through factorization using this algorithm, it is not practical for sampling purpose as we need to repeat the process for all $x_{n+1}\in\mathcal{A}$. We next show an efficient alternative in Section 4.2.

### 4.2 Efficient Next-Byte Sampling Algorithm for P ⁢ ( x n + 1 ∣ x 1 n ) 𝑃 conditional subscript 𝑥 𝑛 1 superscript subscript 𝑥 1 𝑛 P(x_{n+1}\mid x_{1}^{n}) italic_P ( italic_x start_POSTSUBSCRIPT italic_n + 1 end_POSTSUBSCRIPT ∣ italic_x start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_n end_POSTSUPERSCRIPT )

To efficiently compute $P(x_{n+1}|x^{n}_{1})$ for any $x_{n+1}{=}a\in\mathcal{A}$, we note that $\mathrm{cover}(x^{n+1}_{1})$ contains:

- •
$\mathrm{C}_{n+1}(a)$: encodings $\vec{t}$ from the previous $\mathrm{cover}(x^{n}_{1})$ whose $(n+1)^{\mathrm{th}}$ bytes is $a$. Formally, we have: $\mathrm{C}_{n+1}(a){=}\{\vec{t}{\in}\mathrm{cover}(x^{n}_{1})|\mathrm{decode}(
\vec{t}\,)_{n+1}{=}a\}$.
- •
$\bar{\mathrm{C}}_{n+1}(a)$: encodings $\vec{t}$ whose last token starts with $a$ at the $(n+1)$ location. Formally, we have: $\bar{\mathrm{C}}_{n+1}(a){=}\{t^{k+1}_{1}|t^{k}_{1}{=}\mathrm{encode}(x^{n}_{1
}),\mathrm{decode}(t_{k+1}\,)_{1}{=}a\}$.

Since ${\mathrm{C}}_{n+1}(a)\cap\bar{\mathrm{C}}_{n+1}(a)=\varnothing$, then:

$$ $P(x^{n}_{1},x_{n+1}=a)=\sum_{{\mathrm{C}}_{n+1}(a)}P(\vec{t}\,)+\sum_{\bar{ \mathrm{C}}_{n+1}(a)}P(\vec{t}\,),$ (4) $$

With this formulation, we find $\mathrm{cover}(x^{n+1}_{1})$ following the process in Figure 5 ( also see Algorithm 3 in Appendix A.7).
Specifically, to find $\mathrm{C}_{n+1}(a)$ and $\bar{\mathrm{C}}_{n+1}(a)$ for every $a\in\mathcal{A}$, we:

- 1.
Obtain $\mathrm{cover}(x^{n}_{1})$ using Algorithm 1 or from Step 4 of the previous sample.
- 2.
Find $\mathrm{C}_{n+1}(a)$ by checking the $(n+1)^{th}$ byte of each $\vec{t}\in\mathrm{cover}(x^{n}_{1})$. We accumulate them for each $a$ respectively.
- 3.
Find $\bar{\mathrm{C}}_{n+1}(a)$ by querying the conditional distribution over all tokens $P(t_{k+1}|t^{k}_{1})$. Note that $P(t^{k}_{1})$ was already computed in $\mathrm{cover}(x^{n}_{1})$. The encoding accept/reject step is optional.
- 4.
Obtain $\mathrm{cover}(x^{n+1}_{1})$ for all $x_{n+1}=a\in\mathcal{A}$.
- 5.
Sample $x_{n+1}$ from all computed $P(x^{n+1}_{1})$ (normalizing by $P(x^{n}_{1})$).

As a result, we only need to run Algorithm 1 at the beginning of the sampling process. For Step 3, the 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 a large number of encodings at Step 4 by sampling the next byte immediately after Step 3, following Equation (4), and only create the set of the sampled value $x_{n+1}$, i.e. $\bar{\mathrm{C}}_{n+1}(x_{n+1})$.

###### Remark 2 .

Computing $P(x^{n}_{1})$ requires accessing to $P(t_{1})$ but models such as the Yi series (Young et al., ) do not provide $P(t_{1})$. Nevertheless, it is possible to compute $P(x_{n+1}|x^{n}_{1})$ by leveraging the pre-tokenization pattern such as white spaces or punctuation. Details in Appendix A.1.

Figure: Figure 5: Illustration of the sampling process for $x_{n+1}$ from tokenized LM $P(t_{k+1}|t^{k}_{1})$, with example following Figure 4. We do not include $P(\vec{t})$ for simplicity. Details in Section 4.2.
Refer to caption: x4.png

###### Remark 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., ) or mid-word (Dagan et al., ). Token healing (Dagan et al., ; guidance ai, ) mitigates this issue by searching for tokens prefixed with the incomplete word. This method, however, fails to consider all matching possibilities. In the $``\texttt{yummy}"$ example in Figure 4, it can only recover two encodings $``\texttt{yum|my}"$ and $``\texttt{yum|myu}"$ (tokens separated by $``|"$) , as $``\texttt{my}"$ is a prefix string of tokens $``\texttt{my}"$ and $``\texttt{myu}"$, missing $``\texttt{yum|m|yum}"$ (also see Appendix D). Other proposed solution is using specific prompting strategies (Bavarian et al. (), 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 distribution without requiring retraining. Finally, Pimentel & Meister () address a different but related problem of computing next word probability, sharing some similar analysis. Unlike our work, their approach is limited to whitespace-separated 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 to combine multiple LMs. Wan et al. () 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. () 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. () maps the token probabilities of member models to a universal space, which relies on token embedding’s similarity and involves solving an optimization task. Gu et al. () also investigate character-level ensembling, but does not provide expressions for $P(x^{n}_{1})$ or $P(x_{n+1}|x^{n}_{1})$ 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.

## 6 Experiments

### 6.1 Code Completion

Code completion with LLMs is well-suited for our byte-level predictions
because the model is frequently 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-middle (FIM) code completion.
Code completion is the process of taking source code as input along with
a 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 generation provided by pre-training models, nor does it
fit into standard system-user-assistant conversation prompt templates.
The solution has been to introduce a fill-in-the-middle (FIM) prompt template
that turns the middle generation back into a standard prompt that can be
completed by an autoregressive model (Bavarian et al., ).
These FIM prompt templates introduce new tokens or control sequences and cannot
be used with a model that is not aware of them, so code models are
then trained (or fine-tuned) on a dataset of code formatted into
these FIM prompt templates.

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 a code model to
generate the middle portion:
the Prefix-Suffix-Middle (PSM) format "<PRE> {prefix} <SUF>{suffix} <MID>",
and Suffix-Prefix-Middle (SPM) format is "<PRE> <SUF>{suffix} <MID> {prefix}".

Upsides and downsides of PSM and SPM.
The default and most widely-used mode is PSM (Bavarian et al., ; Roziere et al., ).
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 generate by
the control tokens.
While the PSM format solves tokenization issues with this separation,
the downside is 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 a tokenization issue when the prefix stops in the middle of a token.
A standard heuristic to overcoming this in SPM mode is called *token healing*,
e.g., as described in Dagan et al. (),
but it does not correct every tokenization issue here.
These tokenization issues make the PSM template outperform the SPM template
in every previous results for code infilling.

Figure: Figure 6: Pass rates for the HumanEval Random Span benchmark from Bavarian et al. () with CodeLlama-7b for infilling Python. Across all settings, the byte-level predictions yield better completions. We evaluate the two standard infilling prompt templates of Prefix-Suffix-Middle (PSM) and Suffix-Prefix-Middle (SPM), and as a baseline use token healing. The SPM template forces the model to make predictions starting in the middle of a token, which our byte-level predictions successfully handle.
Refer to caption: x5.png

Our results.
We experimented with the standard random-span infilling benchmark from
(Bavarian et al., ).
Figure 6 shows that our byte-level predictions in SPM
mode attain superior performance when using 10 samples,
using CodeLlama-7b.
This corroborates our hypothesis that the contiguity between the prompted
prefix and generated middle in SPM mode is more natural and consistent
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 improvement 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., ).
The recent surge of open-weights LMs, each presumably trained on different subsets of available text, makes these LLMs ideal candidates for bootstrap aggregation.

Figure: Table 1: 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 ensembles outperform single models.

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 prediction, 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 models. In this work, we choose simple averaging. We leave more complex methods for future work.

Figure: Table 2: We evaluate the token and equivalent byte-level model performance of open-weight code LMs. We show the byte-ensemble performance of the top-2 performing models. Ensemble Model achieves best result on Human Eval benchmark while drawing Yi-Coder-1.5B on MBPP.

Benchmarks and setup.
We compare next-token, next-byte and byte-ensembles against one another on multiple knowledge, reasoning, and coding benchmarks. We chose our benchmarks due to their prevalence in testing general LM ability. Due to computational constraints, we test on 7B models primarily.
Note that multiple choice tasks require likelihood evaluation (MMLU, PIQA) while other tasks require mid to long generations.

Our results.
The results of this experiment are in Table 1 and 2. Byte and token predictions are often on par with one another. Ensembling the top-2 performing models seems consistently lead to performance boost except when member model performance is too divergent, as in the case of GSM8K dataset where Yi-1.5-6B outperforms Mistral-7B-v0.3, the second best model, by a margin of 20%. For coding tasks, the ensemble of Yi-Coder-1.5B and CodeLlama2-13b improves up to 3.7% on Human Eval dataset. Overall, these results show the benefits of ensemble as an exciting direction for LMs collaboration.

## 7 Conclusion

Conclusion and limitations.
This work shows that tokenized models have different predictive distributions than their statistically equivalent token-free models, resulting in tokenization bias.
We introduced an O(1) next-byte prediction algorithm to mitigate this bias at inference time. Furthermore, we showed our method to be empirically relevant for FIM benchmarks and model ensemble tasks. However, our method introduces notable memory consumption in its current implementation, and incurs additional linear computational costs (one token = multiple bytes). These factors may limit its practical application in resource-constrained environments at this moment. Even though our work provides new insights into the effects of tokenization, it can not explain or mitigate all related phenomena such as poor performance on arithmetic tasks.

Future work.
While this work sheds some light on token- and byte-level LMs, several open questions 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 to single-token predictions, while real-world applications require generating hundreds 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.
Apart from theoretical work, future development could explore model distillation, where larger models with larger vocabularies could be distilled into smaller models with specialized tokenization. It also enables model-independent prompt optimization, such as for universal adversarial attacks, and facilitates relative uncertainty estimation, allowing for comparisons of model uncertainty.
Our work only scratched the surface of the possibility of model ensembles:
For example, models trained on different languages may outperform a single model trained on all languages simultaneously, as individual models can achieve more optimal entropy bounds by utilizing distinct tokenizations tailored to their respective languages. This might also improve the representation of otherwise underrepresented languages in a training data corpus.
Furthermore, our results also open up new possibilities for tackling mechanism design problems (Duetting et al., ) involving different language models, where the tokenization bias issue can potentially create unfair advantages for certain models.

## Appendix A Appendix

### A.1 Estimate P ⁢ ( x n + 1 | x 1 n ) 𝑃 conditional subscript 𝑥 𝑛 1 subscript superscript 𝑥 𝑛 1 P(x_{n+1}|x^{n}_{1}) italic_P ( italic_x start_POSTSUBSCRIPT italic_n + 1 end_POSTSUBSCRIPT | italic_x start_POSTSUPERSCRIPT italic_n end_POSTSUPERSCRIPT start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ) when P ⁢ ( t 1 ) 𝑃 subscript 𝑡 1 P(t_{1}) italic_P ( italic_t start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ) is not available

In practice, several models such as the Yi series do not provide $P(t_{1})$ since it does not include the beginning of sequence token. As a result, we cannot compute $P(\vec{t})$. However, we can still compute $P(x_{n+1}|x^{n}_{1})$ since their tokenization algorithm often force splitting words by using pre-tokenization pattern such as the whitespace. Let $x_{i}$ be the last whitespace byte in $x^{n}_{1}$ such that $x_{i-1}$ is not a whitespace. Then we know that $t^{k}_{1}=\mathrm{encode}(x^{i}_{1})$ must be the prefix encoding of all cover encodings of $x^{n}_{1}$. This holds not only for $x^{n}_{1}$ but also any string $s=\mathrm{concat}(x^{n}_{1},s^{\prime})$ where $s^{\prime}$ is an arbitrary suffix.

As such, using the BTR Lemma 1, we have:

$$ $\displaystyle P(x^{n}_{1})$ $\displaystyle=\sum_{\vec{t}\in\mathrm{cover}(x^{n}_{1})}P(\vec{t})=P(t^{k}_{1} )\hskip 5.0pt\times\hskip 5.0pt\sum_{\mathclap{\begin{subarray}{c}\vec{t^{ \prime}}\in\mathrm{cover}(x^{n}_{i+1})\end{subarray}}}P(\vec{t^{\prime}}|t^{k} _{1})$ (5) $$

and hence, with factorization:

$$ $\displaystyle P(x_{n+1}|x^{n}_{1})$ $\displaystyle=\left(\sum_{{\begin{subarray}{c}\vec{t^{\prime}}\in\mathrm{cover }(x^{n+1}_{i+1})\end{subarray}}}P(\vec{t^{\prime}}|t^{k}_{1})\right)\hskip 8.0 pt\Bigg{/}\hskip 10.0pt\left(\sum_{{\begin{subarray}{c}\vec{t^{\prime}}\in \mathrm{cover}(x^{n}_{i+1})\end{subarray}}}P(\vec{t^{\prime}}|t^{k}_{1})\right),$ (6) $$

which shows that we do not need $P(t^{k}_{1})$ to compute $P(x^{n}_{1})$, since conditioning on them is sufficient. For autoregressive byte generation, we condition each probability term in Algorithm 3 with $t^{k}_{1}$.

### A.2 Proof of Lemma 1

Lemma 1. (Byte-Token Representation Lemma)
For a consistent tokenizer and a corresponding language model $P(t_{k+1}|t^{k}_{1})$, given a prefix $x^{n}_{1}$, we have the followings:

- 1.
For any distinct $\vec{t}_{i},\vec{t}_{j}\in\mathrm{cover}(x^{n}_{1})$, then $\mathcal{X}(\vec{t}_{i})\cap\mathcal{X}(\vec{t}_{j}){=}\varnothing$.
- 2.
$\mathcal{X}(x^{n}_{1})=\smashoperator[]{\bigcup_{\vec{t}\in\mathrm{cover}(x^{n
}_{1})}^{}}\mathcal{X}(\vec{t})$.

As a result, $P(x^{n}_{1})$ can be expressed as the marginal probability of all covering tokens of $x^{n}_{1}$

$$ $P(x^{n}_{1})=\sum_{\vec{t}\in\mathrm{cover}(x^{n}_{1})}P(\vec{t}).$ (7) $$

###### Proof.

We prove each point as follows:

- 1.
Proof by contradiction, let $t^{i}_{1},t^{\prime j}_{1}\in\mathrm{cover}(x^{n}_{1})$ and $t^{i}_{1}\neq t^{\prime j}_{1}$. Suppose that there exists a sequence $\mathbf{x}$ where $t^{i}_{1}=\mathrm{encode}(\mathbf{x})^{i}_{1}$ and $t^{\prime j}_{1}=\mathrm{encode}(\mathbf{x})^{j}_{1}$. Without the loss of generalization, suppose $i<j$, then $t^{i}_{1}=t^{\prime i}_{1}$ since our tokenizer is deterministic. Hence, $t^{\prime j}_{1}$ cannot be a cover encoding of $x^{n}_{1}$.
- 2.
This follows the definition of cover encodings.

Since each $\mathcal{X}(\vec{t})$ is pair-wise disjoint, we arrive at the final equation.
∎

###### Proof.

### A.3 Proof of Corollary 1

Corollary 1.
We can express $P(x^{n}_{1},t^{k}_{1})$ where $\mathrm{decode}(t^{k}_{1})\in\mathrm{prefix}(x^{n}_{1})$ as follows:

$$ $P(x^{n}_{1},t^{k}_{1})=\sum_{\begin{subarray}{c}\vec{t}\in\mathrm{cover}(x^{n} _{1})\\ t^{k}_{1}=\vec{t}^{k}_{1}\end{subarray}}P(\vec{t}).$ (8) $$

###### Proof.

The proof follows the one for the BTR Lemma 1, where we only consider the cover encodings that start with $t^{k}_{1}$.
∎

###### Proof.

### A.4 Proof of Proposition 1

For completeness, we first show the BPE encoding algorithm in Algorithm 2. For the MPE algorithm, the rule is greedily looking for the longest token that matches the prefix of the given text.

Figure: Algorithm 2 Byte Pair Encoding Algorithm.

Proposition 1.
$\mathcal{X}(t^{k}_{1})=\varnothing$ if and only if $t^{k}_{1}$ is invalid.

###### Proof.

For the case of BPE, we prove each direction as follows.

- •
If $\mathcal{X}(t^{k}_{1})=\varnothing$ then $t^{k}_{1}$ is invalid: Since $\mathcal{X}(t^{k}_{1})=\varnothing$, we know that there exist no sequence $\mathbf{x}$ such that $\mathrm{encode}(\mathbf{x})^{k}_{1}=t^{k}_{1}$. This means there is also no string $s$ that satisfy $\mathrm{encode}(s)^{k}_{1}=t^{k}_{1}$. As such, for $s=\mathrm{decode}(t^{k}_{1})$, we do not have $\mathrm{encode}(\mathrm{decode}(t^{k}_{1}))=t^{k}_{1}$, which proves the result.
- •
If $t^{k}_{1}$ is invalid then $\mathcal{X}(t^{k}_{1})=\varnothing$: Let $x^{n}_{1}=\mathrm{decode}(t^{k}_{1})$, it is sufficient to consider two string $s_{1}$ and $s_{2}$ that both have prefix $x^{n}_{1}$. Furthermore, we assume the first $i$ tokens of $s_{1}$ covers exactly $x^{n}_{1}$, i.e. $x^{n}_{1}=\mathrm{decode}(t^{i}_{1})$ and similarly, the first $j$ tokens of $s_{2}$ covers exactly $x^{n}_{1}$, i.e. $x^{n}_{1}=\mathrm{decode}(t^{j}_{1})$. Then:
1.
Proving invalid $t^{k}_{1}$ leads to $\mathcal{X}(t^{k}_{1})=\varnothing$ is equivalently to proving $t^{i}_{1}=t^{j}_{1}$ for any $s_{1},s_{2}$.
2.
Re-running the BPE algorithm for $s_{1}$ and $s_{2}$ in parallel, we know that there will be no merge between any suffix of $x^{n}_{1}$ and the rest of strings, i.e. $s_{1}\backslash x^{n}_{1}$ and $s_{2}\backslash x^{n}_{1}$ due to the condition above (See Algorithm 2, line 6).
3.
Furthermore, for $s_{1}$, any time a merge happens within $x^{n}_{1}$ then the same merge must also happen within $x^{n}_{1}$ for $s_{2}$ and vice versa.
As the result, we have $t^{i}_{1}=t^{j}_{1}$ and they must be equal to $\mathrm{encode}(x^{n}_{1})$.

For the case of MPE, the proof is similar:

- •
If $\mathcal{X}(t^{k}_{1})=\varnothing$ then $t^{k}_{1}$ is invalid: Since $\mathcal{X}(t^{k}_{1})=\varnothing$, similar to the case of BPE, we know that there exist no string $s$ such that $\mathrm{encode}(s)^{k}_{1}=t^{k}_{1}$. As such, for $s=\mathrm{decode}(t^{k}_{1})$, we do not have $\mathrm{encode}(\mathrm{decode}(t^{k}_{1}))=t^{k}_{1}$, which proves the result.
- •
If $t^{k}_{1}$ is invalid then $\mathcal{X}(t^{k}_{1})=\varnothing$: Let $x^{n}_{1}=\mathrm{decode}(t^{k}_{1})$, we consider two string $s_{1}$ and $s_{2}$ that both have prefix $x^{n}_{1}$. Furthermore, we assume the first $i$ tokens of $s_{1}$ covers exactly $x^{n}_{1}$, i.e. $x^{n}_{1}=\mathrm{decode}(t^{i}_{1})$ and similarly, the first $j$ tokens of $s_{2}$ covers exactly $x^{n}_{1}$, i.e. $x^{n}_{1}=\mathrm{decode}(t^{j}_{1})$. 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.
∎

###### Proof.

### A.5 On Predictive Distribution of Language Models

In practice, LMs 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 probabilities to obey Proposition 1, without any loss in terms of perplexity score on the token domain. In other words, we can turn a 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 distribution $p$ where we know some of the values will not happen, says $\Phi^{*}$. Assume that we have another distribution $q$ 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 $q$ in $\Phi^{*}$ to $0.0$ and renormalize it.

###### Proposition 2 .

Given a discrete distribution $p=\{p_{1},p_{2},...,p_{m}\}$ and $q=\{q_{1},q_{2},...,q_{m}\}$ with $q_{i}>0.0$ for all $i$. Let $\Phi=\{i\in\mathbb{Z}|p_{i}=0.0\}$ and $\Phi^{*}\subseteq\Phi$, we define $q^{*}=\{q^{*}_{1},q^{*}_{2},...,q^{*}_{m}\}$ where $q^{*}_{i}=0.0$ for $i\in\Phi^{*}$, and $q^{*}_{j}=q_{j}/(\sum_{l\notin\Phi^{*}}q_{l})$. Then we have:

$$ $D_{\mathrm{KL}}(p||q^{*})\leq D_{\mathrm{KL}}(p||q),$ (9) $$

which implies that $q^{*}$ is closer to $p$ than $q$. We refer to the process of producing $q^{*}$ as truncate-renormalization (TR).

###### Proof.

Let $Z=(\sum_{l\notin\Phi}q_{l})$ is the normalizing factor in $q^{*}$. Note that $Z\leq 1$ and as such $\log(Z)\leq 0$. Then:

$$ $\displaystyle D_{\mathrm{KL}}(p||q^{*})$ $\displaystyle=\sum_{i}p_{i}\log\left(\frac{p_{i}}{q^{*}_{i}}\right)$ (10) $\displaystyle=\sum_{i\notin\Phi^{*}}p_{i}\log\left(\frac{p_{i}}{q^{*}_{i}} \right)\quad\text{, use }0\log 0=0.0$ (11) $\displaystyle=\sum_{i\notin\Phi^{*}}p_{i}\log\left(\frac{p_{i}}{q_{i}/Z}\right)$ (12) $\displaystyle=\left[\sum_{i\notin\Phi^{*}}p_{i}\log\left(\frac{p_{i}}{q_{i}} \right)\right]+\log(Z)$ (13) $\displaystyle\leq\sum_{i\notin\Phi^{*}}p_{i}\log\left(\frac{p_{i}}{q_{i}} \right)=D_{\mathrm{KL}}(p||q),$ (14) $$

which completes the proof. ∎

Applying to our scenario, for any autoregressive LM $P_{1}(t_{k+1}|t^{k}_{1})$ that does not follow Proposition 1 (due to the softmax activations), we can perform the TR process (since we know which encoding is invalid) to obtain a new LM $P_{2}(t_{k+1}|t^{k}_{1})$, which is guaranteed to better approximate the ground-truth model ${P}(t_{k+1}|t^{k}_{1})$. Thus, we are guaranteed that the token-level perplexity score of $P_{2}(t_{k+1}|t^{k}_{1})$ is always lower than or equal to $P_{1}(t_{k+1}|t^{k}_{1})$. Finally, in practice, we observe that the conditional $P_{1}(t_{k+1}|t^{k}_{1})$ for invalid $t^{k+1}_{1}$ is significantly smaller than the valid tokens.

###### Proposition 2 .

###### Proof.

### A.6 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:

$$ $\displaystyle P(x_{2}=``\texttt{A}"|x_{1}=``\texttt{A}")$ $\displaystyle=\alpha$ (15) $\displaystyle P(x_{2}=``\texttt{B}"|x_{1}=``\texttt{A}")$ $\displaystyle=1-\alpha$ (16) $\displaystyle P(x_{2}=``\texttt{A}"|x_{1}=``\texttt{B}")$ $\displaystyle=\beta$ (17) $\displaystyle P(x_{2}=``\texttt{B}"|x_{1}=``\texttt{B}")$ $\displaystyle=1-\beta$ (18) $$

We also assume the initial probability $\pi=\{\gamma,1-\gamma\}$ for $``\texttt{A}"$ and $``\texttt{B}"$ respectively. In the token domain, let first compute $P(t_{2}=``\texttt{A}"|t_{1}=``\texttt{AA}")$ where we have:

$$ $\displaystyle P(t_{2}=``\texttt{A}"|t_{1}=``\texttt{AA}")$ $\displaystyle=P(x^{6}_{3}=``\texttt{ABA}"|x^{2}_{1}=``\texttt{AA}")+P(x^{6}_{3 }=``\texttt{ABB}"|x^{2}_{1}=``\texttt{AA}")$ (19) $\displaystyle=P(x^{5}_{3}=``\texttt{AB}"|x^{2}_{1}=``\texttt{AA}")$ (20) $\displaystyle=\alpha(1-\alpha),$ (21) $$

where in the first equality, we do not include the case $x^{6}_{3}=``\texttt{AAA}"$ and $x^{6}_{3}=``\texttt{AAB}"$ since $\mathrm{encode}(``\texttt{AAA}")_{1}=``\texttt{AA}"$ and $\mathrm{encode}(``\texttt{AAB}")_{1}=``\texttt{AA}"$, which are not the token $``\texttt{A}"$ that we are interested in. For other tokens when $t_{1}=``\texttt{B}"$, the computation follows the same arguments.

Finally, for the case of $t_{1}=``\texttt{A}"$, we note that it implies the second token must be $``\texttt{B}"$ since any $``\texttt{A}"$ after the first $``\texttt{A}"$ must be tokenized into $``\texttt{AA}"$ (invalid tokens). Hence, we have $P(t_{2}=``\texttt{B}"|t_{1}=``\texttt{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 probabilities of the BTR Lemma (Lemma 1) using the Markov chain’s transition probabilities as ground truth. Specifically, we simulate the data generating process as a 3rd order Markov chain with two states $\mathcal{A}=\{``\texttt{A}"{,}``\texttt{B}"\}$, where we randomly construct the transition matrix and the vocabulary
$\mathcal{V}=\{``\texttt{A}",``\texttt{B}",$ $``\texttt{B}{\cdot}\texttt{A}",``\texttt{BA}{\cdot}\texttt{A}",``\texttt{B}{
\cdot}\texttt{BAA}",``\texttt{A}{\cdot}\texttt{A}",``\texttt{BA}{\cdot}\texttt
{BA}",``\texttt{B}{\cdot}\texttt{B}"\}$. Here, the order within $\mathcal{V}$ is the merging order for the BPE encoding process and the “${\cdot}$” 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.7 Next-Byte Sampling Algorithm

Algorithm 3 shows the next-byte algorithm in Section 4.2. Note that for $\bar{\mathrm{C}}_{n+1}(a)$, we do not need to iterate over every time since the mapping from tokens to their prefix byte can be precomputed (line 30-33).

Figure: Algorithm 3 Compute $P_{\mathcal{A}}(.|x^{n}_{1})$, which is a conditional distribution on $x^{n}_{1}$ over all bytes $x\in\mathcal{A}$. $\mathrm{C}_{n+1}(a)$ and $\bar{\mathrm{C}}_{n+1}(a)$ also contain the encoding probability $P(\vec{t})$ for each encoding they contain.

## Appendix 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 $\mathcal{A}$ that is contained in the vocabularies of all members of our model ensemble: $\max_{\mathcal{A}}\|\mathcal{A}\|\;\;\mathrm{s.t.}\;\;A\subseteq\mathcal{V}_{i
}\;\;\text{for all}\;i$.
This can have certain advantages, the primary one being that generation would be faster: for example imagine an 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 are often based on multiple 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 a universal alphabet, that is the easiest defining the alphabet as 255 bytes and the necessary control tokens.

## Appendix C Ablation: Beam search

Figure: Table 3: Performance increases for the next-byte prediction on our FIM-task when beam search is applied.

Each token is made of 6.6 byte on average. Thus, a tokenized model might have more foresight compared to 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 et al., ; Stahlberg & Byrne, ; Koehn & Knowles, ), this might be different for byte-level models.

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 prompting 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 generation. Since the KV-cache makes about 2/3 of the overall memory consumption beam search is a memory intense operation.

## Appendix D FIM code generation examples

Here, we show three examples from the random span FIM
benchmark from Bavarian et al. () that we evaluate on in Figure 6.
Our greedy byte-level generations significantly improve upon the
greedy token-level generations in the SPM (suffix-prefix-middle) mode
with CodeLlama-7b
because the prompt ends with the “prefix” portion of the code and
the generation starts at a token boundary.
Each figure visualizes an example from the benchmark with the prefix and
suffix at the beginning and separated by $\langle$FILL-ME$\rangle$indicating the portion
for the LLM to generate.
Then, we show the generations from the token and byte-level models in
SPM mode along with token healing as a baseline.
They illustrate exactly where tokenization issues arise when generating
and show how the byte-level predictions correct them.

{listing}
Code generation example with CodeLlama-7b.
This one is interesting because of the typo in the variable “delimeter”
in the dataset and the prefix ends with “delim”.
The misspelled “delimeter” is tokenized as two tokens: “del imeter”
while the correctly spelled “delimiter” is tokenized as a single token.
This makes the 1) token-level prediction incorrectly generate “ter”
as the continuation
because “delimter” is 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, “delimiter” is more likely, and
3) byte-level predictions correctly generate “eter” because
the probability at the byte-level correctly marginalizes out the byte-level
probability despite the context and many possible tokenizations.
{minted}python
# RandomSpanInfilling/HumanEval/5/1
from typing import List

def intersperse(numbers: List[int], delimeter: int) -¿ List[int]:
””” Insert a number ’delimeter’ between every two consecutive elements of input list ‘numbers’
¿¿¿ intersperse([], 4)
[]
¿¿¿ intersperse([1, 2, 3], 4)
[1, 4, 2, 4, 3]
”””
if not numbers:
return []

result = []

for n in numbers[:-1]:
result.append(n)
result.append(delim—$\langle$FILL-ME$\rangle$—mbers[-1])

return result

—token predictions (did not pass ✗):—
ter)
result.append(nu

—token predictions with token healing (did not pass ✗):—
iter )
result.append(nu

—byte predictions (passed ✓):—
eter)
result.append(nu

{listing}
Code generation example with CodeLlama-7b.
This one is interesting because of the tokenization of “collatz”
and the prefix starting with “colla”.
“collatz” is tokenized as two tokens “coll atz”.
This makes the 1) token-level prediction incorrectly generate “zt”
as the continuation
because “collazt” is tokenized as three tokens “col la zt”,
which has a token boundary at the end of the prefix,
2) token-healed predictions incorrectly generate “pse” because at the
token-level after backing up, “collapse” (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.
{minted}python
# RandomSpanInfilling/HumanEval/123/1
def get_odd_collatz(n):
”””
Given a positive integer n, return a sorted list that has the odd numbers in collatz sequence.

The Collatz conjecture is a conjecture in mathematics that concerns a sequence defined
as follows: start with any positive integer n. Then each term is obtained from the
previous term as 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 3 times the previous
term plus 1. The conjecture is that no matter what value of n, the sequence will always reach 1.

Note:
1. Collatz(1) is [1].
2. returned list sorted in increasing order.

For example:
get_odd_collatz(5) returns [1, 5] # The collatz sequence for 5 is [5, 16, 8, 4, 2, 1], so the odd numbers are only 1, and 5.
”””
if nodd_collatz = []
else:
odd_colla—$\langle$FILL-ME$\rangle$— 1

if nodd_collatz.append(int(n))

return sorted(odd_collatz)

—token predictions (did not pass ✗):—
zt = [n]

while n != 1:
if nn = n/2
else:
n = 3*n +

—token predictions with token healing (did not pass ✗):—
pse = []
odd_collatz = [n]
while n != 1:
if nn = n/2
else:
n = 3*n +

—byte predictions (passed ✓):—
tz = [n]

while n != 1:
if nn = n/2
else:
n = 3*n +

{listing}
Code generation example with CodeLlama-7b.
This one is interesting because of the tokenization of “palindrome”
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 the continuation
because “palindrone” is tokenized as four tokens “pal ind r one”,
which has a 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.
{minted}python
# RandomSpanInfilling/HumanEval/107/8
def even_odd_palindrome(n):
”””
iven a positive integer n, return a tuple that has the number of even and odd
integer palindromes that fall within the range(1, n), inclusive.

Example 1:

Input: 3
Output: (1, 2)
Explanation:
Integer palindrome are 1, 2, 3. one of them is even, and two of them are odd.

Example 2:

Input: 12
Output: (4, 6)
Explanation:
Integer palindrome are 1, 2, 3, 4, 5, 6, 7, 8, 9, 11. four of them are even, and 6 of them are odd.

Note:
1. 1 ¡= n ¡= 10^3
2. returned tuple has the number of even and odd integer palindromes respectively.
”””
def is_palindr—$\langle$FILL-ME$\rangle$—odd_palindrome_count = 0

for i in range(1, n+1):
if iodd_palindrome_count += 1
elif ieven_palindrome_count += 1
return (even_palindrome_count, odd_palindrome_count)

—token predictions (did not pass ✗):—
one(n):
return str(n) == str(n)[::-1]

def is_palindrome(n):
return is_palindrone(n) and n ¿= 10

even_palindrome_count = 0

—token predictions with token healing (did not pass ✗):—
eome(n):
return str(n) == str(n)[::-1]

even_palindrome_count = 0

—byte predictions (passed ✓):—
ome(n):
return str(n) == str(n)[::-1]

even_palindrome_count = 0

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: See weakness above. In addition, 

1. Do authors plan to open-source the implementation?

2. 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? 
Token Alignment via Character Matching for Subword Completion https://aclanthology.org/2024.findings-acl.929.pdf
soundness: 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.

The 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.
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.
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.

The 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.

The 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.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: * How is the proposed method compatible with other tokenization algorithms besides BPE and MPE?
* What do the right two sub-figures mean in Figure 6?
soundness: 3
strengths: * This paper defines the tokenization bias phenomenon, which could cause performance issues in practical scenarios. 
* They evaluated the proposed method on FIM code completion task and mode ensemble task. 
* The proposed byte-level prediction method considers both the accuracy and efficiency in recovering the unbiased byte-level distribution.
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.
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. 

* 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? 

* 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?

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
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 ? 

How 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 ? 

In 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.
soundness: 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.
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.
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. 

An area that authors could delve further into is more analysis on the tokenization bias in multi step or long context tasks. 

In 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.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
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$.

I would be willing to change my opinion based on the responses to the weaknesses!
soundness: 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
- The paper is well-written and studies an important problem
summary: Tokenization is a common pre-processing step, which shortens input sequences by mapping multiple bytes to discrete tokens. 
Prior work finds: Even for unlimited data and compute, tokenized models can achieve better cross-entropy loss vs. untokenized models
One hypothesis for why tokenization helps is that it allows models to handle longer contexts at less compute
Main 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.
Approach: this work presents a way to predict when tokenization is getting in the way and converts tokenized LMs into statistically equivalent byte-level models
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.
- 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.
- 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.

Meta-review: The paper raises a problem of tokenization bias, which is a bias in the language model related to the choice of tokens it uses to encode text.  According to the reviews, the problem raised is important, and the analysis for it provided in the paper is clear and thorough. Another strength of the paper is that the provided techniques are both backed by solid theoretical arguments and have convincing empirical evidence showing its value on the selected tasks. 

The reviews raised a few concerns about the paper, asking for a better comparison to selected existing works, and suggested demonstrating the techniques on additional use cases. In the rebuttal, the authors provided a thorough positioning of their paper compared to the works raised in the reviews. The requirement for additional use-cases was not fully resolved in the rebuttal, but it was minor to begin with.  

Though there isn’t a consensus that the paper should be accepted, the techniques seem to be sufficiently motivated, and the edits required to fix the positioning issue seem quite mild. Given the impact of the problem and novelty of the analysis and technique, I think the strengths outweigh the weaknesses and the paper will be a good addition to ICLR.

Decision: Accept (Poster)