UTF-8 Plumbing: Byte-level Tokenizers Unavoidably Enable LLMs to Generate Ill-formed UTF-8

On page 7 of the paper, the authors write “This violates Equation 7, which says that tokenizing and detokenizing an input should return exactly that input. Tokenizers that do not satisfy this property have their own problems that are outside of the scope of this paper.” This surprised me as I believed that tokenizers that do not satisfy that property were one of the key topics of discussion in the paper. On page 1, the authors write: “Detokenization should be a morphism: combining two token sequences and detokenizing them should yield the same result as detokenizing each sequence separately and combining the results.” As this is core to the aims and contribution of the paper, this contradiction significantly weakens the paper.

The sentence you point out on page 7 comes at the end of a discussion on byte-fallback tokenization. The sentence you point out is an error, which we will fix as described in the following paragraph.

Byte-fallback tokenization is a special case of byte-level tokenization where each token in the vocabulary is constrained to be well-formed UTF-8, except for 256 single-byte tokens, each representing one of the 256 bytes. The tokenizer uses these single-byte tokens as a last resort to represent a part of the input that cannot be represented using any of the other tokens in the vocabulary. Because a byte-fallback tokenizer's vocabulary contains tokens that are ill-formed UTF-8 (all the single-byte tokens 0x80 through 0xFF), it is capable of generating ill-formed UTF-8 sequences: this follows from our Proposition 1 ("any vocabulary that contains a member that is ill-formed UTF-8 will be able to generate ill-formed sequences").

There is no substantive contradiction with the remainder of the paper. The passage you point out results from an error in our exposition of byte-fallback tokenization, which, as we have just shown, is covered fully by our framework. Thank you for pointing out our mistake and spurring us to clarify the exposition of byte-fallback tokenization.

The authors claim that the paper advances terminology on this topic, which I do not agree to be a contribution of the paper

The terminological clarity we hope to advance is the explicit use of "byte-level" and "character-level" to describe token vocabularies. Seldom do papers introducing models state explicitly whether their tokenizer works with bytes or characters, though such information is relevant to those implementing downstream applications for those models. We will add clarifying notes on our choices of terminology in the paper's final version.

The authors use the word ‘cutting’ throughout the paper. In most of the paper (second to last paragraph of p.9), this term is being used instead of ‘segmenting’ or ‘tokenizing’. In the final subsection on p. 8, the authors use it instead of ‘pre-tokenization’. The authors at no point in the paper use the term pre-tokenization to refer to that process.

We are happy to vary our term from "cutting" to some other description such as "segmenting" or "chunking". We believe "tokenizing" to be conceptually distinct from "cutting", since "tokenizing" can be represented by a transducer or another formalism, whereas "cutting" refers specifically to our formalism based on monoids.

Another case of imprecise terminology usage concerns the usage of the term ‘detokenization’. It is more common in the literature to refer to this as ‘decoding’ (and the authors do use this term throughout the process to refer to the same concept). The authors should use only one term for clarity.

It is important to distinguish between the process of interpreting a byte sequence according to the UTF-8 encoding scheme and converting a sequence of tokens to a sequence of bytes. We use "decode" for the former and "detokenize" for the latter. In terms of the monoids in the paper, tokenization and detokenization refer to mapping from some $\Sigma^\*$ to some $\Sigma^{\*\circ\wr{}\*}$ and back, whereas encoding and decoding refer to mapping from $\mathrm{B}^\*$ to $\Upsilon^\*$ and back.

If the reviewer thinks using encode and decode are more clear, we are happy to use that terminology, yet we want to maintain a terminological distinction between mapping in and out of the token vocabulary and mapping in and out of UTF-8.

The authors list "tools and code" as a keyword in the paper, however I did not see any code or tools released with the paper. What are the tools and/or code that the paper is contributing?

We selected this keyword because our paper discusses existing tools and codebases.

References

Please see common response for references.

The paper highlights a genuine problem with using UTF-8 encoding. However, the authors motivate this problem theoretically without highlighting the empirical evidence of this problem (https://arxiv.org/pdf/2410.23684) [4].

Thank you for the reference. The problem [4] examines is distinct from our own. They show how to construct improbable but well-formed sequences of characters from models' vocabularies and that these sequences cause undesireable behavior in models. This vulnerability is similar to that caused by glitch tokens [2,3], where undertrained tokens cause bad behavior in models. Both issues stem from undertrained tokens or sequences of tokens forcing the model into generating a sequence distant from any in its training data.

We show that the presence of ill-formed tokens in the model's vocabulary permit the model to generate sequences of bytes that are not well-formed UTF-8. The presence of ill-formed UTF-8 in the output presents a vulnerability to systems that work with LLMs and expect their inputs and outputs to be well-formed UTF-8. [2,3,4] all exclude ill-formed sequences from their analyses.

The authors do not sufficiently engage with the literature on this topic.

Thank you for the detailed bibliographic citations. Since you raise several points in this question, we shall treat them one at a time.

Of the efficacy of BPE: we are not invested in the superiority of any cutting algorithm over another. In other words, we are not concerned with where $\Sigma^{*\wr\circ}$ comes from. BPE and Unigram are both members of the class of tokenizers covered by our formalism, as are any other algorithms that work by producing a finite vocabulary and cutting inputs such that each part of the input between the cut marks is a member of the vocabulary. We merely point out a problem that will affect any byte-level tokenizer, regardless of how the vocabulary is determined. Discussing the pros and cons of BPE as a compression algorithm for producing subword vocabularies is not in the scope of our paper, though we appreciate the references to expand our related work section.

"Glitch tokens" are undertrained tokens in the model's vocabulary and are distinct from the ill-formed UTF-8 sequences we discuss, though the latter also cause glitches. [3] discusses what they call "partial UTF-8" tokens, defined as "tokens representing byte sequences that cannot be converted to Unicode characters [decoded, in our terms] as they contain only part of the full UTF-8 encoding for a character." This is a special case of our ill-formed tokens: ill-formed byte sequences need not contain any part of a UTF-8 encoding form. Ill-formed tokens are explicitly excluded from [3]'s experiments because they "are not suitable for building verification prompts", presumably because these prompts must be well-formed UTF-8 to work with existing interfaces (e.g. Huggingface's).

Our language of character-level and byte-level would clarify [3]. In particular, [3] section 3.1.1 describes character-level tokenizers with byte-fallback and point out the interesting bug that these vocabularies include both a single-character token and a byte-fallback token for all the ASCII characters, code points U+00 through U+7F, which UTF-8 encodes as themselves (see our Appendix B). This is a crucial bug in these models, precisely because it introduces glitch tokens by necessity, but one that is hard to understand because their paper does not discuss it this clearly.

ASCII byte-fallback tokens are a source of very glitchy tokens (see [2] Figure 23, in the Appendix) and one that is important to be explicit about for those models that use character-level tokenizers with byte-fallback. [2] exclude byte-fallback tokens from their Figure 9 in the main body of the paper, which figure reports the glitchiest tokens in the Llama 2 vocabulary. They drop these tokens presumably because they are unreachable [3], namely, they cannot be the product of ordinary tokenization. However, attackers that control the tokenization process could force these tokens into the input of a model in a way that would be concealed on the output, since the detokenization process converts these byte-fallback tokens into the bytes they represent.

We clarify this discussion in a novel, explicit way, and thereby contribute to the discourse by permitting the disambiguation of the role of bytes, characters, and byte-fallback tokens in tokenization.

The term “code points” is used multiple times (including in the abstract) before it is defined on p. 5. The authors should either define this in the introduction or use a different word to refer to this, which does not require definition.

We will clarify this in the next version of the paper. Thank you for the feedback.

It's not clear what the value of adding the stochastic dimension is. It doesn't play any role here.

We include stochasticity to show that the problem is not unique to deterministic tokenizers; should one implement a tokenizer that returns multiple possible tokenizations, or retokenizes the input dynamically on line according to some assessment of the probability or semantic aptness of a given tokenization, the same problem of potentially ill-formed UTF-8 would be present. Although deterministic tokenizers are currently more common, it is possible that future LLMs will use stochastic tokenizers, which might result in more robust models [5, 10, 13].

Other works analyzing BPE (e.g. [11, 12]) assume that the algorithm is deterministic or have to cope with the ways it might not be. We include the mention of stochasticity to explicitly announce that we do not assume this about the tokenizers we study; deterministic tokenizers are included a fortiori because they are a special case of stochastic tokenizers where the probability distribution is such that exactly one tokenization has a probability of 1 and all others have a probability of 0.

The homomorphism proof seems solid but would be easier to follow if homomorphism were actually defined explicitly

Thank you for pointing out the inconsistency, which we shall resolve in the next version of the paper.

The general assumption seems to be that we might encounter characters we've not seen before. Is this realistic? It's certainly true, but unless the text sample is really small, do these new characters ever really matter?

Rare and out-of-vocabulary characters may arise in practice. We include the multiocular o ꙮ as an example in Table 2 because it appears once in all of written Old Church Slavonic but is nevertheless present in models' training data via Wikipedia. Even if the vocabulary does not contain a single token for ꙮ and has to break it down into bytes, those bytes have appeared in the model’s training set, which allows the model to make use of those tokens for meaningful inference.

There are a number of undefined items, e.g. serving engine and foundation model.

We will clarify the definition of these terms in the next version of the paper. Thank you for pointing this out.

I was suprised to see no explicit contact with the finite-state literature. I think this is more opportunity than problem though.

We considered and chose not to use the abstraction of transducers [8] for our description of tokenization.

The general proposal seems to be: have a buffer. Is this new? It looks like a number of systems have strategies that are like what's proposed here, so it's not clear what this paper offers except perhaps a deeper understanding of the issue.

Algorithm 1 is presented to document behavior that is already present in deployed systems. The contribution we offer is a formal proof that ill-formed UTF-8 sequences are always possible for models that have vocabularies containing tokens made up of ill-formed UTF-8, as well as a formalization of the relationship between tokens, bytes, and UTF-8 encoding forms.

References

Please see common response for references.

Algorithm 1 is presented as a workaround, not a fundamental fix—it avoids errors but introduces unbounded memory risk.

The buffer in the pseudocode of the algorithm is an abstraction of an implementation trick whereby one indexes into the array of generated tokens to keep track of the last sucessfully-decoded token. The memory cost of Algorithm 1 is no greater than the storage of the generated tokens, plus the storage for the pointer into the array.

While the theoretical analysis is excellent, the paper stops short of offering new tokenizer designs that inherently satisfy morphism and UTF-8 constraints.

We show that there is no simple solution to this problem: if the tokenizer is able to produce an arbitrary sequence of tokens from its vocabulary, and the vocabulary contains tokens made up of ill-formed UTF-8, then the model will be able to produce ill-formed UTF-8 sequences.

Could your impossibility theorem be extended to cover other encodings (e.g., UTF-16, UTF-32) or only applies to UTF-8?

No, it only applies to UTF-8. We will add a note clarifying this in the next version of the paper. UTF-8 is used by the vast majority of web sites, is the standard encoding used by programming language standard libraries, and is the format used to transmit data sets used to train large language models and thus our work primarily focuses on UTF-8.

Have you observed model output behavior (e.g., hallucinations, truncation) that can be directly attributed to UTF-8 detokenization errors?

One author experienced a crash in an interactive LLM application while generating the Coptic Small Letter Sima ⲥ. We believe this to have been caused by the interface's attempting to decode the model's output token-by-token, failing entirely because the letter was represented by multiple tokens, the first of which was ill-formed.

The mitigation strategies are not fully benchmarked in terms of latency or robustness across model sizes. How does Algorithm 1 affect streaming performance in real deployments?

The latency of the incremental decoding is negligable compared to the cost of generating tokens and can be performed in parallel with generation. Our tests on a MacBook M1 Pro with vLLM's and TGI's implementations of this algorithm result in a latency of less than 0.001s/token. On the same machine, generating a token with Qwen3-8b takes about 0.05s/token. The cost of detokenization is constant with regard to model size.

Are memory buffers manageable at inference scale?

The memory buffer in our algorithm is an abstraction of the implementation trick of indexing into the array of input ids the model has generated to keep track of the position of the last successfully-decoded token; there is no memory overhead beyond storing the model's output itself and the constant memory required for the pointers.

Heavy reliance on abstract algebraic notation and formal language theory (monoids, morphisms) may limit accessibility for practitioners. It is difficult to follow the paper.

Thank you for the comment. A future revision will include more examples and clarify the introduction.

References

Please see common response for references.

Can you clarify the difference between monoid $\Sigma^{\*}$ and $\Sigma^{\*\wr\circ{}\*}$ in Definition 7?

The monoid $\\Sigma^\*$ is all possible finite sequences of members of $\Sigma$ (e.g. $\mathrm{abcd}$). The monoid $\Sigma^{\*\wr}$ is the set of all possible finite sequences of members of $\Sigma$ with squiggles pre- and postpended (e.g. $\wr{}\mathrm{abcd}\wr{}$). $\Sigma^{\*\wr\circ}$ is a finite subset of $\Sigma^{\*\wr{}}$ and is intended to represent the vocabulary of a given tokenizer (e.g. $\{\wr{}\mathrm{abc}\wr, \wr{}\mathrm{def}\wr, \wr{}\mathrm{acf}\wr\}$. Then $\Sigma^{\*\wr\circ{}*}$ contains all possible sequences of members of $\Sigma^{\*\wr\circ}$ and is intended to represent all possible sequences that can be made using the vocabulary of a given tokenizer (e.g. $\wr\mathrm{abc}\wr\mathrm{acf}\wr$; note that we elide adjacent squiggles for readability).

In principle, we could say $\Sigma^{\*\circ\wr}$, which would be a finite subset of $\Sigma$ with a squiggle pre- and postpended to each of its members, instead of $\Sigma^{\*\wr\circ}$. We believe that the distinction does not matter formally, though the choice between them could be motivated by clarity of exposition.

Proposed solution (i.e. Algorithm 1) to the problem is not applicable to real-world systems due to unlimited memory costs (which can break a running system when confronted with malicious user)

The memory buffer in Algorithm 1 is an abstraction of the implementation trick used in deployment of indexing into the array of generated input ids to keep track of where the last successfully-interpreted encoding form ends. The pointer is advanced when more tokens are successfully decoded. There is no memory overhead beyond storing the input ids the model has generated and the pointer into that array.

Some more examples are needed along the formalized theoretical framework which helps the reader to better understand the formal definitions.

Thank you for the comment. We will incorporate examples in the next version of the paper.

Contribution Nr 4. states that a fundamental problem is due to "incremental detokenization" but I don't see where this is inferred from the theoretical framework introduced in Section 3. This conclusion needs to be made more explicit.

In a future revision, this contribution will be rephrased to something like "We show that decoding a sequence of tokens as UTF-8 can violate formal assumptions about the properties of tokenizers, such as their being lossless or homomorphisms." Thank you for pointing out the inconsistency.

In Algorithm 1, what is epsilon?

The empty string. This will be stated more clearly in the next version of the paper.

How do you deal with an increasing buffer which does never see a well-formed UTF8 sequence?

Algorithm 1, as deployed, always returns an empty string in this case.

What do you exactly refer to with "cell" in the text explaining Table 1?

The cells in question are the vertical columns of the table, one for each code point. These are separated by space, but in the next version of the paper we will distinguish more clearly between them.

I suggest to shortly explain the term "monoid" if you use it in the Introduction section.

Thank you for the comment. We will clarify the introduction in the next version of the paper.

References

Please see common response for references.

Why are Monoids necessary for illustrating the problem? Are there more straightforward approaches to show the existence of the problem?

We found monoids to be a natural abstraction to formalize our problem. A monoid structure for a language (i.e. a space defined by a finite set of elements that can be concatenated to one another form sequences) is already common in the literature on combinatorics on words. To give examples from the tokenization literature, the structure of monoids describes the assumptions [14, 15] make about their algorithms' inputs. The primary alternative formalization we are aware of would be to use transducers [8], which we believe would significantly complicate the presentation.

The solution proposed in this paper is the standard incremental decoding algorithm, which is not novel at all.

Algorithm 1 documents a solution already present in deployed tools such as vLLM, OpenLLM, and TGI. We provide it to document an ad hoc solution that arose to this problem in the wild. Our paper formalizes the problem of ill-formed UTF-8 in byte-level tokenizer vocabularies, which will always permit the generation of ill-formed byte sequences.

What are the differences between the algorithm proposed and the incremental decoding algorithm that are implemented in, say, Python?

Our Algorithm 1 is an abstract generalization of the implementations in Python used by the serving engines surveryed.

How does Algorithm 1 react when it never reaches a correct UTF-8 token? How resilient is Algorithm 1 in terms of the extent to which the raw byte string is erroneous?

Algorithm 1 will simply return the empty string indefinitely, never successfully decoding anything. This is in fact the behavior of deployed systems.

The evaluation only compares with SynCode on a set of tasks with singular goals and doesn't compare with other works like GCD, Guidance, automata-based constraint decoding, etc. How are other constraint decoding schemes affected by this problem?

We also examined Synchromesh and observed the same issue. Given the focus of our paper on a theoretical impossibility result, we focused our evaluation on these two popular tools. As we demonstrate, other constraint decoding schemes will also have to cope with incomplete or ill-formed UTF-8 in their inputs.

The problem itself is fairly simple and highly restrictive. The paper formalizes the problem with the Monoid theory but made little to none theoretical contributions regarding nontrivial results or novel techniques.

Our main contribution is a proof that the presence of tokens containing ill-formed UTF-8 in a byte-level tokenizer's vocabulary makes it possible to produce sequences of tokens that are never valid UTF-8. This has real impacts in production, as acknowledged by reviewers uy5s, MUTr, x3kb, and cvmT. Our use of the monoid formalism to prove this property and our ability to predict and detect the presence of software bugs support the value and interest of our contribution.

References

Please see common response for references.

The main motivation behind this paper is to argue detokenization must be a morphism, because otherwise malformed UTF8 is possible. However, as the authors note, this is important only in token-by-token streaming.

Ill-formed UTF-8 is not only important in token-by-token detokenization. It is possible for the model to take in or put out sequences of tokens that contain ill-formed UTF-8 at any point within the sequence. Attempting to interpret such a sequence of bytes as UTF-8 will lead to errors caused by ill-formed bytes.

Token-by-token streaming sees wide deployment: the serving engines TGI, OpenLLM, and vLLM all use token-by-token detokenization. Huggingface transformer's logits processors also work with model outputs token-by-token.

The algorithm 1 that the authors propose has already been implemented by various different open-source implementations and is therefore not entirely novel.

As stated in the paper, Algorithm 1 is not our primary contribution. We contribute a mathematical formalization of the problem of ill-formed UTF-8 byte sequences, which can always be generated by a byte-level tokenizer's vocabulary. By presenting it to the community, we open the problem up to scientific exploration and debate.

This algorithm does not provide guarantees that the decoding process will lead to valid UTF8 and only solves the problem for common issues.

We prove that there is no such guarantee where the model is allowed to generate tokens that are ill-formed UTF-8. The only way to guarantee that the model only generates well-formed UTF-8 at each step of generation is to make sure that each token in the vocabulary is well-formed UTF-8.

The biggest question I have with this is why not try to use constrained decoding to go further than Algorithm 1, and implement a grammar/constraints that guarantee no invalid UTF8 sequences of tokens?

Thank you for suggesting this approach. Constraining generation to only allow valid UTF-8 would prevent the model from generating any character whose bytes stretched across multiple tokens. When the first token containing the beginning of the character's bytes had been generated, the overall sequence would be ill-formed until the next tokens with the remaining bytes had been generated.

You note that ablations on tokenizers are seldom performed but some previous work in multilingual [6] and code generation [7] have done ablations at small scale -- though more looking at tokenizers from the perspective of compression.

Thank you for pointing out examples of ablations on tokenizers; we will incorporate these examples in the next revision of the paper. We note that none of the models in Table 3, which we believe to be a representative sample of contemporary large foundation models, underwent ablations on their tokenizers.

References

Please see common response for references.