UTF-8 Plumbing: Byte-level Tokenizers Unavoidably Enable LLMs to Generate Ill-formed UTF-8
Authors: Preston Firestone
Shubham Ugare
Gagandeep Singh
Sasa Misailovic
Venue: COLM 2025 (2025)
Keywords: tokenization
TL;DR: Byte-level subword tokenization creates vocabularies whose tokens aren't well-formed utf-8, requiring workarounds to interpret as code points.

Abstract: Subword tokenization segments input text according to a pre-defined vocabulary to feed it into a language model; the language model, in turn, generates a sequence made from this same vocabulary. The members of the vocabulary can be built of code points or bytes. Using code points means that all members of the vocabulary are valid UTF-8 characters. However, it also requires thousands of initial members to achieve acceptable coverage of inputs. Beginning with bytes, on the contrary, avoids out-of-vocabulary errors with only 256 initial members of the vocabulary, but the members of the vocabulary and sequences of them are not guaranteed to be valid UTF-8. Sequences that are not valid UTF-8 break code that assumes its input to be valid UTF-8. Applications of language models must account for the breakage thereby introduced. In this paper, we formalize tokenization using monoid theory and prove that tokenizers whose vocabularies contain tokens that are ill-formed UTF-8 can always produce sequences that are ill-formed UTF-8. We demonstrate formally that attempting to incrementally convert tokens back to a string and interpret the results as UTF-8 gives different results than converting the whole sequence of tokens at once. This formal result predicts real-world bugs: we evaluate mitigations for the problem identified and provide case studies of major foundation models, serving engines, and constrained generation systems.

Published as a conference paper at COLM 2024
UTF-8 Plumbing: Byte-level Tokenizers Unavoidably Enable LLMs to Generate Ill-formed UTF-8
Preston Firestone
Shubham Ugare
Gagandeep Singh
Sasa Misailovic
University of Illinois Urbana-Champaign, USA
Abstract
Subword tokenization segments input text according to a pre-defined cabulary to feed it into language model; the language model, in turn, generates sequence made from this same vocabulary. The members of the vocabulary can be built of code points or bytes. Using code points means that all members of the vocabulary are valid UTF-8 characters. However, it also requires thousands of initial members to achieve accept- able coverage of inputs. Beginning with bytes, on the contrary, avoids out-of-vocabulary errors with only 256 initial members of the vocabulary, but the members of the vocabulary and sequences of them are not guar- anteed to be valid UTF-8, Sequences that are not valid UTF-8 break code that assumes its input to be valid UTF-8. Applications language models must account for the breakage thereby introduced. In this paper, for- malize tokenization using monoid theory and prove that tokenizers whose vocabularies contain tokens that are ill-formed UTF-8 can always produce sequences that are ill-formed UTF-8. We show formally that attempting incrementally convert tokens back a string and interpret the results as UTF-8 gives different results than converting the whole sequence of to- kens at once. This formal result predicts real-world bugs: we evaluate mitigations for the problem identified and provide case studies of major foundation models and constrained generation systems.
1 Introduction
Large language models (LLMs) compute the probability of a given sequence of tokens drawn with replacement from finite vocabulary. Tokenization is the process of cutting input string into tokens such that each token is member of a predefined vocabulary. Tra- ditionally, tokenization used prior knowledge of the language, such as words, morphemes, or phonemes, to separate the text into useful elements (Grefenstette & Tapanainen] 1994] Palmer 2000). Contemporary natural language processing has moved to using "subword" tokenization, where the vocabulary is derived automatically from a corpus of texts rather than programmed manually (Mielke al.) 2021).
The text the tokenizer works with is stored in computers as bytes. In order to interpret these bytes characters meaningful to humans, we must define an encoding scheme mapping between sequence of bytes and sequence of characters. The predominant scheme is called UTF-8, regulated by Unicode Technical Committee (2025 $3.4, 3.9.3, 3.10). As of 2025, UTF-8 is used by 98.5% of all websites (W3 2025) and is required by the W3C for user agents (van Kesteren 2024 $4.2).
two examples of strings as characters, bytes, and tokens, from different lan- guages and models. Contemporary language models' tokenizers typically work with the bytes on the bottom row of Figure rather than the characters on the top row. Abstracting away the bytes to focus on the characters is an instance of a "leaky" abstraction, a common issue in software engineering: the information that tried to hide by abstraction ends up being exposed (often as we need to handle errors) (see Spolsky 2002 Kiczales et al. 1992 Kiczales 1991).
1

---

Published as a conference paper at COLM 2024
31
(a) Characters and bytes representing the opening of the Rigueda (Sanskrit: Tfp)), "an=fthā" translit- erated agnim ile ("I praise Agni [fire]"), tokenized according cl100k_base.
T
P
a
л
a
I
И
JI
a
ID0 93t
ID1
BO
DO BA
120
DO B3:
[D1
BO
DO B42
(DO
DO BB
DO BO?
(b) The first two words of The Building of Skadar (Serbian Cyrillic: 3anane Cxanpa), "I paa rpamat"" transliterated Grad gradila ("The city was built"), tokenized according to Qwen3's vocabulary.
Figure 1: Examples UTF-8 encoding. each subfigure, the top row contains the in- dividual Unicode characters that compose the string (see Uniccde Technical Committee 2025 $2.11), and the bottom row contains the UTF-8 bytes that encode each character in the string; each byte is represented by two hexadecimal numerals. The squiggles indicate the boundaries between tokens.
Concretely, concatenating tokens made up of bytes does not always result in sequences that can be successfully interpreted as characters. In Figure la the first token, 2EO A41, does not encode any character by itself; only when combined with the second token 1857 can the resulting three bytes EO A4 85 be interpreted as the character sanskrit. Since lan- guage models generate sequences made up of the tokens in their vocabulary rather than generating bytes directly, programs that interact with sequences generated by language model must handle byte sequences that cannot be interpreted characters.
Contributions. this paper, we make the following contributions:
Introduce formal framework for tokenization based monoid theory.
* Prove, using our formalism, that vocabularies containing tokens that cannot be inter- preted characters can always produce sequences that cannot be interpreted charac- ters.
Show that interpreting bytes as UTF-8 characters is not a homomorphism and formally represent common mitigation strategies in the framework of monoids. Classify popular language models according the type of tokenizer they use.
Fix failures in constrained generation.
2 Background on monoids
To treat tokenizers abstractly, we introduce a formalism based on monoids, common in the literature combinatorics words (Sakarovitch) 2009 Lothaire 1997) but to our knowledge new to natural language processing.
(Free) monoids. The basic component of abstraction is the monoid.
Definition 1 (Monoid). monoid triple composed of tion on members of that set, and an identity element. We refer to monoids by Greek capital letters (E), their members by subscripted lowercase Latin letters (s E), the binary op- eration as subscripted dot (<z), and the identity element as subscripted epsilon (Ez). A sequence of members of a monoid is referred by a lowercase Greek letter (o = 5o ' $1). Subscripts and binary operations are left out when context makes the meaning clear.
elements, binary opera-
Monoids' binary operation is associative but not commutative. For members of the monoid,
(s1 1 52) I $3 = 51 z (52 x 93).
(1)
The identity element is neutral element for the binary operation, such that for any se- quence 0
T 3g = -x-zz=
(2)
2

---

Published as a conference paper at COLM 2024
Set theoretical operations ==,., are defined between monoids that share binary operation and an identity element.
An example monoid is a language, where the symbols that make up the language are the set of members $0 ... concatenation the binary operation 'I, and the empty string the iden- tity element eg. In subsequent sections we will reason about all the sequences that can be formed from given monoid, which make up the free monoid of a given monoid.
Definition 2 (Free monoid). The free monoid generated by a monoid Σ, denoted Σ², is the monoid of all sequences of finite length made of elements from Σ. The free monoid is like the Kleene closure over the set of members of Σ, except the free monoid only contains finite sequences.
In Section we will use the free monoid to describe the set of all sequences that can be generated with given vocabulary, and in Section 4 we will use a free monoid describe all byte sequences that can be interpreted as string.
Properties of monoids and their free monoids. We will need to compare the contents of the free monoids of two different monoids that share binary operation and identity element; this will allow us to make claims about what kinds of sequences are and are not in given free monoid.
Lemma 1. If some monoid Σ contains member not in some other free monoid A', where E and A share a binary operation and an identity element, then the free monoid E* of the first monoid E also contains members not in the other free monoid A
Σ
Proof. Suppose for contradiction that there exist some and A such that Σ E A and Σ* C A"; the existence of such pair would be a counterexample to Lemma For the set of members of Σ not be subset of A* there must exist some member of that is not in A*. That member of Σ is also in Σ*, but that implies that Σ g A*. This contradiction shows that no counterexample
Lemma T exxists, thereby proving that the implication holds for
all monoids Σ and A that share a binary operation and an identity element.
L
Mapping between monoids. In order to describe the process of tokenization in Section we will need to map sequences back and forth between different monoids. To that end we introduce the abstraction of a stochastic map (Gastaldi et al. 2024
Definition (Stochastic map). A stochastic map from monoid E to monoid A is function from Σ to the set of probability distributions on A.
Other works analyzing tokenizers (e.g. Zouhar et al. 2023b Geng et al. 2024 van Antwer- pen & Neubeck 2024) assume that the tokenizer is deterministic or have cope with the ways it might not be. Following Gastaldi et al. (2024) we use stochastic maps to ensure that our results apply to nondeterministic tokenizers, which might result in more robust models (Geh et al. 2025 Chai et al. 2024a Hofmann et al. 2022). Similarly, in our notation we do not explicitly depict the probability distribution over tokenizations that returns, because we do not examine the probability of individual tokenizations, but merely which tokenizations are or are not possible for a given input.
We introduce the property of homomorphism as restriction maps:
Definition& 4 (Homomorphism) A map x from monoid Σ to A is homomorphism if and only if, for all o, o' Σ,
x(r x(()) x(('))
(3)
We show in Section 3 that tokenizing a string is not homomorphism and in Section that interpreting bytes string is also not homomorphism. We then discuss real-world mitigations (Section 5) and bugs that arise because tokenizers fail to be homomorphisms (Section
3

---

Published as a conference paper at COLM 2024
3 Tokenization described with monoids
Using the tools we introduced, we describe tokenizer a pair of stochastic maps between two monoids and prove that tokenizing is not a homomorphism.
Binding and cutting monoids. We need to describe, in terms of monoids, the process of cutting that a tokenizer does to its input. The system we introduce in this subsection is similar but not identical to the system Berglund van der Merwe (2023). See Section for a comparison of our system with theirs.
Definition 5 (Cut monoid). The cut monoid of given monoid is a monoid each of whose members has been prepended and postpended by squiggle 2. The cut monoid of given monoid is indicated by a superscripted squiggle:
Σ' = {1or 2 lo E ]}
(4)
Where convenient do so, we collapse adjacent squiggles for legibility,
For convenience, we use the notation E to name finite subset of some monoid Σ; we call the operator "bind". All three operators, cutting (t), binding (o), and freeing (+), can be applied in succession to single monoid, which we depict by putting multiple superscripts on the capital Greek letter representing the monoid; the operations are applied in order from left to right.
We next illustrate our notation and define several monoids relevant in the rest of this paper. The monoid E* is all possible finite sequences of members of E. The monoid Σ is the set of all possible finite sequences of members of Σ, each sequence with squiggle pre- and postpended to it-it represents the set of all possible tokens. E is finite subset of E represents the vocabulary of some tokenizer. * contains all possible sequences of members of I- represents all sequences that can be made using the vocabulary of given tokenizer.
What is a tokenizer? Tokenization is cutting the input into tokens. We define it as pair of mappings between two monoids Σ' and E- that share a binary operation and identity element:
Definition 6 (Tokenizer). We call tokenizer over some free monoid E* and some vocab- ulary y pair of stochastic maps T: E + + and K y + Σ*
The map T cuts its argument such that each token of the cut sequence is a member of some the vocabulary I X joins the cut sequence by removing all the cut operators t. is deterministic and works the same way for any vocabulary made from the same initial monoid, whereas the behavior of T depends on its vocabulary. Each tokenizer (T, is parameterized by the vocabulary E it is defined over, but we omit this detail in the notation because we will only work with one vocabulary at a time. We will refer to passing some input through T as tokenizing and some input through x as detokenizing
Tokenizers and homomorphism. In the paper, will rely on the following property of tokenizers as we defined them in Definition 6
Theorem Given a tokenizer (T, k), K a homomorphismm, but is not.
Proof. x is a homomorphism: The result of concatenating two cut sequences and removing the cut marks is always identical to removing the cut marks and concatenating them: the cut symbols are removed and the resultant string is identical to its uncut version. We have shown that there
counter examples to Equation for
T is not homomorphism: Take some 50 ... Sn E Σ and cut into some 28p S. Sm Sm+1 i 5m42 Sgl. It is impossible to separately cut 60 S....Spp Sm and Sm+1 ... S, such that there is not
I Thouuh the standard in the literature is to use "decode" for x, we chose an alternative term "deto- kenizing" to make it clear that we are speaking of turning tokens into some sequence of members of the uncut monoid, a step consider separately from the process of interpreting those bytes as UTF-8 string.
4

---

Published as a conference paper at COLM 2024
cut after Sm and before Sm+1i therefore the concatenation of any separate cutting of the
two sequences Sp 55 and Sm++1 1 ...... Sy must include the subsequence Sm Sm+1- Cutting the entire sequence -. at once allows for sequences that do not contain Sm 25m 11. We show that there exist counterexamples to Equation for
Theorem ] has already been proved by Geng et al. (2024), though they use different approach from ours. We reprove the Theorem here to exercise our system and state in
our terms, and extensively use it in Section 4 Theorem applies to any tokenizer that uses cutting, regardless of vocabulary, the order in which cuts are applied, and whether the tokenization stochastic not.
Out-uf-vocabulary errors. Sometimes there does not exist any way to cut a sequence such that the resulting cut sequence is made up exclusively of members of the tokenizer's vocab- ulary. Often, however, at least part of the input can be cut into members of the vocabulary. There are three basic ways to deal with sections of the input that cannot be represented in the vocabulary: failing entirely, dropping the unacceptable section, and replacing the section with something else. In terms of our formalism:
Failing entirely: declaring to undefined where its input cannot be mapped to E 2. Dropping an unacceptable section: replacing the sequences between squiggles that are not in Ix with lēy, (this is special case of the replacement strategy where 7/ e); 3. Replacing the section with other symbols: mapping the objectionable bytes, according to some scheme, to one or more members of E specially set aside for this purpose
A T that uses any of these mitigations will not be a homomorphism, because none of the mitigations avoids the counterexample given in the proof of Theorem [ UTF-8 implemen- tations often elect the third option, replacing ill-formed byte sequences with "replacement character", U+FFFD (?).
UTF-8 and monoids
The UTF-8 encoding scheme. In the UTF-8 encoding scheme (Unicode Technical Com- mittee 2025, $3.9.3), each character is paired with some byte sequence one four bytes long; single such byte sequence is called a UTF-8 code unit. Descriptions of the UTF-8 code units are found in Table any sequence of bytes made up exclusively of concatenated, non-overlapping UTF-8 code units is a well-formed UTF-8 string. See Appendix B for more details about Unicode and UTF-8. The rest of this sec- tion will discuss UTF-8 using the monoid and tokenizer abstractions we introduced earlier. We begin by phrasing the encod- ing of characters bytes and the interpre- tation of bytes as characters in terms monoids.
First byte
Second byte
Third byte
Fourth byte
00.7F
C2..FF
80.
E0
AO..BF
8O..BF
EL.EEC
80.
80..
HD
80.9F
80..
EE..FF
80.
80..BF
FO
90.
80..BF
80..
FI..F3 F4
80.
80..BF
80..FF
80.8F
80..BF
80.
Table 1: Well-formed UTF-8 byte se- quences (Unicode Technical Committee 2025 $3.9.3). A range such 80..BF should be read as an inclusive range from 80 through BF
Definition 7 (UTF-8). We refer to the monoid of UTF-8 code units as Y, which is the B specified in T The sequences of B" that are not in Y* are ill-formed UTF-8 sequences; the members of B that are in Y* well-formed.
Not all byte sequences well-formed UTF-8; see Appendix B for examples. The exis- tence of byte sequences that are ill-formed in UTF-8 motivates Theorem 2 which follows immediately from Lemma 1 and Definition 7
2See Unicode Technical Committee 2025 53.9.6 and van Kesteren 2024
$4.1) for the standard
algorithm for this replacement.
5

---

Published as a conference paper at COLM 2024
Theorem 2. Any vocabulary B4 that contains byte sequence & that is ill-formed in UTF-8 (B & Y* will be able to generate ill-formed sequences:
Bato
g Y + B g Y*
Due to Theorem 2 any language model's vocabulary that contains byte tokens ill-formed in UTF-8 can generate token sequences that are ill-formed in UTF-8.
Enforcing UTF-8 breaks homomorphism in tokenizers. Section we will show impacts of assuming that the output of language model is well-formed UTF-8. To prove that the problems we discuss are inevitable, we introduce the following theorem.
Theorem 3. Interpreting a byte sequence as UTF-8 is not a homomorphism, but serializing sequence of well-formed UTF-8 byte sequences is homomorphism.
Proof. Mapping between bytes and well-formed UTF-8 sequences is like tokenization, as in Definition/6] Mapping from well-formed UTF-8 sequences to a sequence of bytes means simply concatenating those bytes (Unicode Technical Committee 2025 $3.10). Joining the UTF-8 code units into byte string is naturally like detokenizer x from Y* (i.e. B*t to B' Mapping from a sequence of bytes to a well-formed UTF-8 sequence requires splitting that byte sequence into consecutive, adjacent UTF-8 code units. This is like a from B" to
Y (i.e. B*oos). Theorem 3 follows directly by application of Theorem
Theorem 3 applies regardless of which of the strategies of Section 3 is used. In the next
section, we will assume that decoding applies the third strategy discussed in Section 3 and we will refer to the member of Y set aside for ill-formed byte sequences number of yss used to replace ill-formed bytes in the sequence and their identity is variable.
1j. The
In Section 6 we will examples where more than one distinct replacement character exists. See Unicode Technical Committee (2025) $3.9.6) ) for the standard algorithm used for replacement when decoding UTF-8. The process assumes a single !J, the character U+FFFD | "replacement character". The number of yss introduced to suture any ill-formed sections of the byte sequence will not be relevant to the results of the next section, only that such unique character exists.
Incrementally detokenizing ill-formed UTF-8 sequences
is common for language model applications stream or otherwise incrementally gen- erate tokens, decoding and displaying the decoded tokens opportunistically. Interactive systems, for example, can display the intermediate steps of the generation to the user; hosted language models remote server might send tokens to the client soon they become available, rather than wait for generation to complete before sending anything downstream.
As we have shown in Section 4 certain combinations of tokens can be ill-formed UTF-8, causing process that attempts decode them apply one of the coping strategies of Subsection 3 The decoding processes used in deployed tokenizers use the third strategy described at the end of Section "replacing the [ill-formed] section with other symbols", in particular they use the symbol U+FFFD ("replacement character"); our formalism calls 1t.
If the user attempts to interpret the byte tokens as UTF-8 as the tokens come in, then con- catenate, the result will different from what the user would have gotten had they waited for all the tokens before interpreting them all together. This problem was detected in serv- ing engines for language models, which host language models and serve them through an API locally over the network: these engines failed to generate correct text, because they incorrectly assumed that the conversion from bytes to well-formed UTF-8 was a homo- morphism. This problem and common mitigation strategy were introduced to Hugging Face TGI by a user's 's issue (Hugging Face, 2025 0x1997 2023) and percolated thence to
vLLM (Kwon et al. 2023: Yard 2023), OpenL.M (bentom) 2025 2025 jeffwang0516 2023), and

---

Published as a conference paper at COLM 2024
SGLang Zheng et al. 2024 hnyls2002 2024), all of which faced similar issues for the same reason. See Appendix for a Python code from the serving engines.
@norrithmmformaliieee this mitigation strat- egy using the framework of monoids. The opportunistically function ADVANCETOKEN C interprets byte tokens as UTF-8 sequences when the end of the sequence's final token is aligned with the edge between two code points. Each time is called, ADVANCE- TOKEN receives all the tokens generated so far, with the new token at the end of the sequence. If there is a new well-formed code unit the end of the sequence of to- kens, ADVANCETOKEN updates i and j to point the last two positions in the token sequence where the token and code unit boundary lined up and returns the new successfully-decoded code units. The al- gorithm ignores the tokens before the 7th token, because appending bytes to well- formed UTF-8 cannot change the previous code units: well-formed UTF-8 code units do not overlap.
Algorithm 1 Incrementally generate using byte-level tokenizer.
Require:
T: B Y". Tokenize sequence of bytes to a sequence of UTF-8 code units, replacing ill-formed bytes with 1/.
k Ba B" Detokenize from
quence of byte tokens in some vocabu- lary B* to sequence of bytes.
-M Bu - B A language model that takes in a sequence of tokens and returns new token.
stateful integer initialized to O. j: stateful integer initialized to O.
1: function ADVANCETOKEN B: B*tar)
2:
Y Txx(B|i: fD)
LENCTH(()))) :':Y" + ([x( LEX
3:
4:
if LENGTHH()" LENGTH(U)
D"LLENGH(('' - then i itj
The outer function, GENERATE, shows how to exercise ADVANCETOKEN to emit the in- crementally produced text as well-formed code units are completed. Both the byte to- kens and text generated so far are stored in the local variables B and u, which en- ables the generating process to output text as it is generated without losing informa- tion about the exact bytes the model gen- erated. Note the binary operations on lines and 6 of the function GENERATE in Algo- rithm 1 the first concatenates bytes and the second UTF-8 code units. The purpose of Algorithm [ is to enable the simultaneous application of these operations without destructively decoding the byte tokens such that further tokens cannot be successfully appended to the sequence.
5:
6:
j - LENGTH(B)
7:
return J'LLENGT((D):
LENGTH(U')]
8: else
9:
return CY
function GENERATE
2:
p: 1 + éB
3:
U: Y c
4:
loop
5:
B- B BB LM(B)
6:
U 'Y ADVANCETTOKEN(1. B)
7:
EMIT(B, v)
Algorithm cannot make concatenating UTF-8 tokens a homomorphism (consistent with Theorems and 3 If one attempted to concatenate two sequences in Y* that came out of the function GENERATE, one would always end up with sequence in Y*. But if the se- quences in B that Algorithm detokenizes and decodes as UTF-8 are not well-formed UTF-8, then the outputs of Algorithm [ will remove or mangle the information the ill- formed bytes contained. For example, the text of Figure la contains twelve tokens. De- coding the first five with Algorithm produces the UTF-8 code units "3TT"; decoding the remaining seven produces "? f concatenating produces "3FT ?
1
the ex- pected "अाсगीीī"" Dropping the ill-formed bytes, strategy 2 from Section 3 will not restore homomorphism: "3 "MA'" "अnrÍt""" not "аpиパий.. Algorithm is not always nec- essary: none of the Cyrillic characters in Figure 1b are split across more than one token, while several of the Devanagari characters Figure la are. Detokenizing and decoding this Cyrillic sequence is a homomorphism as special case, because all of its tokens are well- formed; correctly handling the Devanagari sequence, on the other hand, requires special handling.
7

---

Published as a conference paper at COLM 2024
The information lost when decoding an ill-formed byte sequence (whether failing, drop- ping, or replacing) is always gone. Concatenating the decoded tokens will therefore pro- duce different results from decoding the concatenated tokens wherever the split between tokens is not aligned with the split between code units. Algorithm î decodes the interme- diate results of generation while correctly appending new tokens to those generated far. The local variable v in the function GENERATE always contains the code units generated so far; if the final code unit is the filler character y/ (2),, then v does not contain the final code unit. Because it appends
the tokens' monoid B as well in the code units' monoid Y (see lines 5 and 6 of the function GENERATE), Algorithm 1 is a partial fix for certain cases, but as we have seen, has inherent limitations.
6 Sealing the leaks in UTF-8 decoding
Deployed tokenizers usually concatenate byte tokens and interpret them as if they were UTF-8; when the process reaches ill-formed subsequence, it has the choices outlined in Section failure, dropping, and replacement. Theorem 3 shows that vocabulary contains byte tokens that are ill-formed UTF-8, it will be able to produce sequences that are ill-formed UTF-8. We next classify the tokenizers of common foundation models and discuss coping with the impacts of T'heorem in constrained generation.
Tokenization strategies of foundation models. In Table 2 we classify several popular language models according to the style of tokenizer they use. We find two broad categories: byte-level, and byte-fallback. Byte-level tokenizers impose no constraints on the formation of tokens, which may or may not be valid in UTF-8. Since all non-ASCII characters are represented by more than one byte in UTF-8, any script that uses a character other than the 128 in ASCII could have its characters split across multiple tokens by a byte-level tokenizer.
Byte-fallback tokenizers require that all tokens in the vocabulary be valid in UTF-8, with the exception 256 (or 243, excluding the 13 bytes that never appear in any UTF-8 code unit) tokens, one for each byte. These extra tokens are used to represent parts of the input that cannot otherwise be represented by tokens in the tokenizer's 's vocabulary. Figure 2 gives example of such tokenization, where each of the tokens contains valid UTF-8 string, except for the three single-byte tokens used to encode the rare character & ("multiocular o", used in a single manuscript from the 15th century). Theorem plppliess to both strategies equally, because the single-byte tokens are already ill-formed and so sufficient condition for the theorem.
M
i
ID BC: (DO BD DO BE DO B3 DO BE?
[EA i 1991 AEI (D1 87 DO BS DI 821
(D1 971
(DO B91
Figure Characters and bytes representing the Old Church Slavonic word mHoro uurii, transliterated mmogoočitii ("many-eyed"), tokenized according to the vocabulary of Gemma-3,
Model
Tokenizer Type
OpenAl since GPT-2 (Radford et al. 2019
Brown
2020
OpenAl al. 2024
Byte-level
Qwen, Qwen2.5, Qwem3 (Bai et 2023
Yang al. 20256
Byte-level
Llama 1,2 (Tovvron el al. 20233
Byte-fallback
Ilama GGattationi et a1. 21/4
Byte-level
Mistral, Mixural (Mang 21 2023 2024
Byte-fallback
Gemma 1, 2, (Mesnard al 2124 Lemma Team et al. 2024 2025
Byte-fallback
OLMo, OLMo Groenevell el 2024 Team ML 2525
Byte-level
Phi-1, 1,5, (Gunasckar al
avaheripi Bubeck Microsoft al. 2025
Byte-level
Phi-3 (Abdin et al, 2024
Syte-fallback
Cohere R an (Cohere 2024
Byte-level
Stable LM I, 2 (Stability-Al belagente et al. 2024
Byte-level
CodeGen, CodéCen2 NNijkamp al. 20235:1
Byte-level
Table 2: Foundation models and the tokenizers they use.
8

---

Published as a conference paper at COLM 2024
Eight out of ten of the model families classified in rabli the same style of tokeniza- tion throughout their generations. Llama changes from SentencePiece (Kudo & Richard- son 2018) to vocabulary derived from OpenAl's tiktoken (OpenAl 2025) for its third generation (Grattafiori et al. 2024). This change of dependencies resulted in a switch from byte-fallback (since Sentence enforces UTF-8 validity on its tokens by default, the only mitigation it offers for covering out-of-vocabulary inputs is byte-fallback) to byte-level. Phi-3, unlike the other Phii-series models, used Llama 2's vocabulary; Phi-(1, 1.5) use vo- cabularies from CodeGen; Phi-2's documentation does not describe the tokenization in de- tail, but manual inspection of the publicly-available vocabulary reveals it to be byte-level; and Phi-4 uses one of OpenAl's vocabularies from tiktoken [OpenAl| 2025), all of which are byte-level. As we discuss in Section 7 ablations are seldom performed on tokenizers, and none of the models in Table 2 tested with more than one tokenizer. We presume that the reason for skipping ablations is the excessive cost training multiple models of the same scale and architecture but with distinct tokenizations (and embeddings).
Existing constrained generation systems and non-homomorphic tokenizers. Constrained generation techniques are used to restrict language model outputs to adhere to specified rules. We examined various grammar-constrainer generation systems and tested them to discover their behavior during partial generation decoding (Scholak et al.
2021; Poesia
iet al., 2022: Willard & Louf 2023 Ugare et al., 2025b a Banerjee et al. 2025 Loula et al.
2025 Suresh et al. 2025). Among popular rrammar-constraing
generation tools, we found
that that Synchromesh (Poesia et al. 2022) and SynCode (Ugare et al. 2025b) encountered issues
when grammars included non-AsCII characters such emojis or mathematical symbols such as '." Both tools use character-based parsers rather than byte-based ones, which created this vulnerability.
The way to fix this problem is to constrain generation at the level of bytes rather than characters. Attempting to constrain at the level of characters fails where the bytes of the token are ill-formed UTF-8. For example, the character V, used in Lean (Moura & Ullrich 2021,, might be tokenized (E2 88 801. If the model has generated the first token of the character, then the constrained generation algorithm must permit the second token as continuation, even though neither of the tokens is well-formed. Constraining at the level of bytes rather than characters by using bytes as the input alphabet for lexers, DFAs, and so forth repairs this problem.
For the v0.3.0 release of SynCode, we replaced the previous character-level finite state machines with byte-level ones. To evaluate SynCode's ability to handle non-ASCII Unicode charac- ters, we conducted an experiment us- ing an emoji generation task. We se- lected subset of the TweetEval emoji
Metric
SynCode v0.2.0
SynCode v0.3.0
Accuracy Crash Rate
0%
62%
100%
0%
Table 3: Performance comparison between Syn- Code versions on emoji generation task
dataset |Barbieri et al. (2020), filtering for three common emoji classes. The task required the model to generate exactly one emoji character in response to a given tweet, adhering to a constrained grammar specification (see listing g in Appendix B). We evaluated this
task across 100 examples from the TweetEval test set on two versions of SynCode: v0.2.0 which used character-level constraints, and the current version which implements byte- level constraints. Performance improvements are reported in Table v0.2.0 crashed on all examples, whereas v0.3.0 successfully generated emojis for all examples.
Related work
We direct the reader to Appendix for more related work.
Formal approaches to tokenization. Following Sakarovitch 2009) and Lothaire (1997), treat languages monoids. Monoids have found use the analysis of formal lan- guages (Yang & Wu 2023) but hardly at all in the study of natural languages. The work of Joachim Lambek on type grammar has led him to study natural language in terms of

---

Published as a conference paper at COLM 2024
ordered monoids (Lambek) 1997 2007), but his work came to our attention too late to sig- nificantly impact our work here.
UTF-8 challenges in tokenization. Rahman et al. 2024, SIL.D) discuss the challenges of UTF-8, both because it encodes characters as sequences of varying length, and many char- acters are encoded by more than one byte. The latter challenge cannot be avoided unless one wants to limit one's character space to 256 unique characters, but the former issue is unique to UTF-8 and distinguishes it from other encoding schemes, UTF-16 and UTF-32, which encode all code points in two and four bytes respectively.
Ablations. To our knowledge, ablations the relative efficacy of byte-fallback and byte- level tokenization have not been performed, [Dagan et al. (2024) ablate on datasets, pre- tokenization schemes, and vocabulary size; :el:Ailiii et al. (2024 ablate on datasets, tokenization algorithms (BPE v. Unigram) and implementations (Hugging Face v. SentencePiece). None directly address the tradeoffs between byte-level and byte-fallback tokenization.
Glitch tokens. "Glitch tokens" are under-trained tokens in the model's vocabulary that
can cause erratic behavior (Land & Bartolo, 2024 Geiping al. 2024). They are distinct
from the ill-formed UTF-8 sequences we discuss. Land & Bartolo (022)) discuss what they
call "partial UTF-8" tokens, defined as "tokens representing byte sequences that cannot be converted to Unicode characters [decoded, in our terms] 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 UTF-8 encoding form. Ill-formed tokens are explicitly excluded from Land & Bartolo 2024)'s 'ss 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. Hugging Face's).
The byte-fallback tokens (see Section 6 that encode the bytes of ASCIT characters source of glitchy tokens (see
(see|Geipin Geiping et al. 2024 Figure 23, in the Appendix), Geiping et al. (2024) exclude byte-fallback tokens trom the in the main body of the paper that reports the glitchiest tokens in the Llama 2 vocabulary, because the tokens that represent the bytes of the ASCII characters cannot be the result of ordinary tokenization.
Improbable bigrams. Jang et al. (2024) examine pairs of tokens made up of tokens that are not well-formed UTF-8 but that, when concatenated, make a well-formed byte sequence. These tokens enable make attacks similar to those Land & Bartolo (2024; Geiping et al. (2024), with the difference that Jang al. (2024) examine pairs tokens, whereas Land & Bartolo (2024); Geiping et al. (2024) examine individual tokens. These bigrams are well- formed and distinct from our examination of ill-formed sequences.
8 Conclusions and future work
The paper shows that UTF-8, tokens, and strings are leaky abstractions when generating text using language models. Rather than burying the issue, practitioners should accustom themselves to not expecting the inputs or outputs of their LLM system to be well-formed UTF-8. Implementers of systems and applications for language models should test their implementations on non-ASCII characters and ensure that they behave properly when an input generated sequence is ill-formed UTF-8. Authors should be more precise when specifying the tokenization scheme their model uses when describing its architecture. We leave for future work surveying more foundation models, testing language model applica- tions, expanding Algorithm [ for concatenation in both directions rather than just append- ing (though we note that behaves correctly when appending an arbitrarily large number of new tokens), and experimenting with multiple constrained generation algorithms.
All humans have the right to interact with computers in their own language and to be able to use computers to generate and manipulate text, with equal regard to all languages. This paper works toward that goal by clarifying some common issues present with large language models. It has addressed leak in one of the abstractions used to work with lan- guage, but the general problem of how to process all natural languages uniformly remains open.
10

---

Published as a conference paper at COLM 2024
Acknowledgments
We thank the anonymous reviewers for their comments. This research was supported in part by NSF Grants No. CCF-1846354, CCF-2313028, CCF-2238079, CCF-2316233, CNS- 2148583, and an Amazon Research Award.
Ethics statement
Davis & Suignard 2014) describes security issues that face systems that interact with Uni- code as closely as language model applications and infrastructure must. They describe non-visual exploits such as buffer overflows during encoding decoding, text compari- son, ill-formed input bytes, including several exploits that are particular to UTF-8. Davis & Suignard 2014)'s visual exploits are based visual spoofs, visually mistakable strings: these are two or more different sequences code points that appear the same to the user (see (nicode Technical Committee (2025) $3.11) and Davis et al. (2024)). These would be tokenized differently by all tokenizers, because they are not the same byte or code point sequence and so cannot be represented by the same tokens.
Visual spoofs can be used for attacks similar to those recently studied by Geh et al. (2025) where models generated radically different responses varying tokenizations of the same prompt; in some cases Geh et al. (2025) broke safety and alignment restrictions trained into models. visual spoof would circumvent a mitigation Geh et al. (2025) suggest for their attack: providers of language models as service could prohibit users from tokenizing their own texts and require them to submit well-formed UTF-8 in order to avoid adversarial tokenizations. Visual spoofs could produce the same effect of adversarial tokenization without the user needing to have direct control over the tokenization process.
When discussing how to decode UTF-8 sequences, the Unicode standard offers the follow- ing foreboding words: "[s]ilently ignoring ill-formed sequences strongly discouraged because joining text from before and after the ill-formed sequence can cause the resulting text to take new meaning. This result would be especially dangerous in the context of textual formats that carry embedded program code" (Unicode Technical Committee, 2025 C10). This warning is particularly apt for processes executing code that a language model generated.
11

---

Published as a conference paper at COLM 2024
References
0x1997. Missing and garbled characters when streaming unicode text. GitHub Issue, 2023.
htthp::::///gthhbb wtt. http://gg.nnnaaaeeeeeeeeeeeeeeer
Marah Abdin, Jyoti Aneja, Hany Awadalla, Ahmed Awadallah, Ammar Ahmad Awan, Nguyen Bach, Amit Bahree, Arash Bakhtiari, Jianmin Bao, Harkirat Behl, et al. Phi-3 technical report: A highly capable language model locally on your phone, 2024. URL
2404. httoss//arill.or//bb//444111. 14219
Orevaoghene Ahia, Sachin Kumar, Hila Gonen, Jungo Kasai, David Mortensen, Noah Smith, and Yulia Tsvetkov. Do all languages cost the same? tokenization in the era of commercial language models. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Proceedings of the 2023 Conference on Empirical Methods in Natural Language Process- ing, pp. 9904-9923, Singapore, December 2023, Association for Computational Linguis- tics. doi: 10.18653/v 2tt.:/3/vv222..emmmmmm main.614. ma1.mm6.. emnlp-main. 614/
URL http::://aclanthologg.o org/ 20233.
Mehdi Ali, Michael Fromm, Klaudia Thellmann, Richard Rutmann, Max Lübbering, Jo- hannes Leveling, Katrin Klug, Jan Ebert, Niclas Doll, Jasper Buschhoff, Charvi Jain, Alexander Weber, Lena Jurkschat, Hammam Abdelwahab, Chelsea John, Pedro Or- tiz Suarez, Malte Ostendorff, Samuel Weinbach, Rafet Sifa, Stefan Kesselheim, and Nico- las Flores-Herr. Tokenizer choice for LLM training: Negligible or crucial? In Kevin Duh, Helena Gomez, and Steven Bethard (eds.), Findings of the Association for Compula- tional Linguistics: NAACL 2024, pp. 3907-3924, Mexico City, Mexico, June 2024. Associ- ation for Computational Linguistics. doi: 10.18653 20133//11/22//// /2024. findings-naacl222 fttts:://allanthooogggooor//////
URL
findings-naaci. 247/
Jinze Bai, Shuai Bai, Yunfei Chu, Zeyu Cui, Kai Dang, Xiaodong Deng, Yang Fan, Wenbin Ge, Yu Han, Fei Huang, Binyuan Hui, Luo Ji, Mei Li, Junyang Lin, Runji Lin, Dayi- heng Liu, Gao Liu, Chengqiang Lu, Keming Lu, Jianxin Ma, Rui Men, Xingzhang Ren, Xuancheng Ren, Chuanqi Tan, Sinan Tan, Jianhong Tu, Peng Wang, Shijie Wang, Wei Wang, Shengguang Wu, Benfeng Xu, Jin Xu, An Yang, Hao Yang, Jian Yang, Shusheng Yang, Yang Yao, Bowen Yu, Hongyi Yuan, Zheng Yuan, Jianwei Zhang, Xingxuan Zhang, Yichang Zhang, Zhenru Zhang, Chang Zhou, Jingren Zhou, Xiaohuan Zhou, and Tian- hang Zhu. Qwen technical report, 2023. URL htt.h:ts///axii.org/abaosss//
16609,
Debangshu Banerjee, Tarun Suresh, Shubham Ugare, Sasa Misailovic, and Gagandeep Singh. Crane: Reasoning with constrained Ilm generation. In Forty-Second International Conference on Machine Learning, 2025. URL https://ccml.c////rrru//////////
43624
Francesco Barbieri, Jose Gamacho-Collados Leonardo Neves, and Luis Espinosa-Anke. Tweeteval: Unified benchmark and com comparative evaluation for tweet classification, 2020. URL
12421
Marco Bellagente, Jonathan Tow, Dakota Mahan, Duy Phung, Maksym Zhuravinskyi, Reshinth Adithyan, James Baicoianu, Ben Brooks, Nathan Cooper, Ashish Datta, Meng Lee, Emad Mostaque, Michael Pieler, Nikhil Pinnaparju, Paulo Rocha, Harry Saini, Han- nah Teufel, Niccolo Zanichelli, and Carlos Riquelme. Stable Im 1.6b technical report, 2024. /tthttss://aaxx wrg./bb/////....../ http://///ara...or////////222222 17834
bentoml. OpenLLM. OpenLLM
GitHub Repository, 2025. URL https://github. com/ bentoml/
Martin Berglund and Brink van der Merwe. Formalizing bpe tokenization. Electronic Pro- ceedings in Theoretical Computer Science 388:16-27, September 2023. ISSN 2075-2180, doi: 10.4204 /2224//pccs.88.44 URL http: www.:odoi..og//i// 4204//ETCS. 388.PPTCS.888..
Kaj Bostrom and Greg Durrett. Byte pair encoding is suboptimal for language model pre- training. In Trevor Cohn, Yulan He, and Yang Liu (eds.), Findings of the Association for
12

---

Published as a conference paper at COLM 2024
Computational Linguisties: EMNLP 2020, pp. 4617-4624, Online, November 2020. Associ- ation for Computational Linguistics. Linguigssss doi: 10. 10.18653/v1 11120..inding--emae
URL
findings-emnlp. 414/
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners, 2020. URL https://arxiv..n org/ ataaabss//000 14165
Yekun Chai, Yewei Fang, Qiwei Peng, and Xuhong Li. Tokenization falling short: On sub- word robustness in large language models. In Yaser Al-Onaizan, Mohit Bansal, and Yun- Nung Chen (eds.), Findings of the Association for Computational Linguistics: EMNLP 2024, Pp. 1582-1599, Miami, Florida, USA, November 2024a. Association for Computational Linguistics. doi: 10.18653/v /1 22//22222.f.ii. 1024.findings-emnll... URL htttps://ccaattiiinn org/2024. finiafiiinnnnnseennln 86/
Yekun Chai, Qingyi Liu, Jingwu Xiao, Shuohuan Wang, Yu Sun, and Hua Wu. Au- toregressive pre-training on pixels and texts. In Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen (eds.), Proceedings of the 2024 Conference on Empirical Methods in Natu- ral Language Processing, pp. 3106-3125, Miami, Florida, USA, November 2024b. Asso- ciation for Computational Linguistics. doi: 10.18653/ve 20/55/3v1/224.mm/// /20//22222llppp.. manilp-mmain1122... URL https: https://aclantiooooy..oor///// wttp:///222....emmaaaaaa.. emnlp-main. 182/
Jonathan H. Clark, Dan Garrette, Iulia Turc, and John Wieting. Canine: Pre-training
an efficient tokenization-free encoder for language representation. Transactions of the Association for Computational Linguistics, 10:73 91, 01 2022. ISSN 2307-387X. doi:
10.1162/tacl___0044a URL /ttphttts///oo..rg/// 1162/tac1, a_ 00448
Marco Cognetta and Naoaki Okazaki. Tokenization as finite-state transduction, 2024. URL https://arxtw.org/bbs////
15696
Marco Cognetta, Vilém Zouhar, Sangwhan Moon, and Naoaki Okazaki. Two counterex- amples to tokenization and the noiseless channel. In Nicoletta Calzolari, Min-Yen Kan, Veronique Hoste, Alessandro Lenci, Sakriani Sakti, and Nianwen Xue (eds.), Proceedings of the 2024 Joint International Conference on Computational Linguistics, Language Resources and Evaluation (LREC-COLING 2024), pp. 16897-16906, Torino, Italia, May 2024. ELRA and ICCL.
lrec-main 1469/
Cohere. The command model (details and application), 2024.
Gautier Dagan, Gabriel Synnaeve, and Baptiste Rozière. Getting the most out of your tokenizer for pre-training and domain adaptation, 2024. URL htttps://arxiv.org/aa
2102.01035
Mark Davis and Michel Suignard. Unicode security considerations. Unicode Technical Report 36, Unicode Consortium, 2014. http:://www.niiicddde.rr//rrr//s
Mark Davis, Martin Dürst, and Ken Whistler. Unicode normalization forms. Unicode Stan- dard Annex 15, Unicode Consortium, 2024. URL
tr15/
Matthias Gallé. Investigating the effectiveness of BPE: The power shorter sequences. In Kentaro Inui, Jing Jiang, Vincent Ng, and Xiaojun Wan (eds.), Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 1375-1381, Hong Kong, China, November 2019, Association for Computational Linguistics. doi: 10.18653/ v1 11/119-1141. URL
13

---

Published as a conference paper at COLM 2024
Juan Luis Gastaldi, John Terilla, Luca Malagutti, Brian DuSell, Tim Vieira, and Ryan Cot- terell. The foundations of tokenization: Statistical and computational concerns, 2024.
B.KLnttts:///axxi.orrr//as 2407. 11606]
Renato Lui Geh, Zilei Shao, and Guy Van den Broeck. Adversarial tokenization, 2025. URL https://ariiv..or///b///55....
Jonas Geiping, Alex Stein, Manli Shu, Khalid Saifullah, Yuxin Wen, and Tom Goldstein. Coercing Ilms to do and reveal (almost) anything, 2024. URL htttps:/aaxxiv.org/aa 2402. 14020
Gemma Team, Morgane Riviere, Shreya Pathak, Pier Giuseppe Sessa, Cassidy Hardin, Surya Bhupatiraju, Léonard Hussenot, Thomas Mesnard, Bobak Shahriari, Alexandre Ramé, et al. Gemma 2: Improving open language models at a practical size, 2024. URL 001 18
Gemma Team, Aishwarya Kamath, Johan Ferret, Shreya Pathak, Nino Vieillard, Ramona Merhej, Sarah Perrin, Tatiana Matejovicova, Alexandre Ramé, Morgane Rivière, al. Gemma 3 technical report, 2025. URL https://///aaxx http//aaiiii..rg/////5/3... 19786
Saibo Geng, Sankalp Gambhir, Chris Wendler, and Robert West. Byte bpe tokenization as an inverse string homomorphism, 2024.
Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, et al. The llama 3 herd of models, 2024. URL httthhttt///reee httpa///aaaxi..o//a//////22
21783
Gregory Grefenstette and Pasi Tapanainen. What is word, what is sentence?: problems of tokenisation. 1994.
Dirk Groeneveld, Iz Beltagy, Pete Walsh, Akshita Bhagia, Rodney Kinney, Oyvind Tafjord, Ananya Harsh Jha, Hamish Ivison, Ian Magnusson, Yizhong Wang, Shane Arora, David Atkinson, Russell Authur, Khyathi Raghavi Chandu, Arman Cohan, Jennifer Dumas, Yanai Elazar, Yuling Gu, Jack Hessel, Tushar Khot, William Merrill, Jacob Morrison, Niklas Muennighoff, Aakanksha Naik, Crystal Nam, Matthew E. Peters, Valentina Pyatkin, Abhilasha Ravichander, Dustin Schwenk, Saurabh Shah, Will Smith, Emma Strubell, Nishant Subramani, Mitchell Wortsman, Pradeep Dasigi, Nathan Lambert, Kyle Richardson, Luke Zettlemoyer, Jesse Dodge, Kyle Lo, Luca Soldaini, Noah Smith, and Hannaneh Hajishirzi. Olmo: Accelerating the science of language models, 2024. URL https://arxiv. https://arxxv.orr//bb//222.2
wttpobgg///bb//////o/ee 200.s//400..800 00838
Suriya Gunasekar, Yi Zhang, Jyoti Aneja, Caio César Teodoro Mendes, Allie Del Giorno, Sivakanth Gopi, Mojan Javaheripi, Piero Kauffmann, Gustavo de Rosa, Olli Saarikivi, al. Textbooks are all you need, 2023. URL h/tpt:://////xiv..... httrgaabb/330..115// 11644
hnyls2002. Decode incrementally. GitHub Pull Request, 2024. URL https: com/ 5gl [Bl-project//sllan//ull///
Valentin Hofmann, Hinrich Schuetze, and Janet Pierrehumbert. An embarrassingly simple method to mitigate undesirable properties of pretrained language model tokenizers. In Smaranda Muresan, Preslav Nakov, and Aline Villavicencio (eds.), Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume Short Papers), pp. 385-393, Dublin, Ireland, May 2022. Association for Computational Linguistics. doi: 10.18653/
URL htRLlttsss///dantoollyy.oo////// acttssott 43/
Hugging Face. Text generation inference, 2025. URL text- -eneeerrrtiio-nnferenneee inference
Huggingface. tokenizers. huggingfaace/tokenizes,
GitHub Repository, 2025. URL. https://github.com
Eugene Jang, Kimin Lee, Jon Chung, Keuntae Park, and Seungwon Shin. Improbable expose expose vulnerabilities incomplete tokens in byte-level tokenizers, 2024. URL 23684
14

---

Published as a conference paper at COLM 2024
Mojan Javaheripi and Sébastien Bubeck. Phi-2: The surprising power of small language models.
jeffwang0516. bug: Output text from completionchunk is different with tokenizer.decode.
Github Issue, 2023. htLphhtts///gthhuut com
Albert Q. Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lu- cile Saulnier, Lélio Renard Lavaud, Marie-Anne Lachaux, Pierre Stock, Teven Le Scao, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed. Mistral 7b, 2023. https:
06825
Albert Q. liang, Alexandre Sablayrolles, Antoine Roux, Arthur Mensch, Blanche Savary, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Emma Bou Hanna, Florian Bressand, Gianna Lengyel, Guillaume Bour, Guillaume Lample, Lélio Renard Lavaud, Lucile Saulnier, Marie-Anne Lachaux, Pierre Stock, Sandeep Subramanian, Sophia Yang, Szymon Antoniak, Teven Le Scao, Théophile Gervet, Thibaut Lavril, Thomas Wang, Tim- othée Lacroix, and William El Sayed. Mixtral of experts, 2024. URL htths:/://// 04088
G. Kiczales. Towards new model of abstraction in software engineering: In Proceedings 1991 International Workshop on Objec! Orientation in Operating Systemss, pp. 127, 127,128, 128, Los Alamitos, CA, USA, October 1991. IEEE Computer Society. doi: (001109//WOOSS..0 183036. URL (ttL:httss://d/// wew.cooottttsssscctttyooooooomm
1109/IW000S 1991. 183036
G. Kiczales, M. Theimer, and B. Welch. A new model of abstraction for operating system design. In [1992] Proceedings of the Second International Workshop on Object Orientation in Operating Systems, pp. 346-349, 1992. doi: 10.1109 /11./////0000000.222222222
Terry Koo, Frederick Liu, and Luheng He. Automata-based constraints for language model decoding, 2024.
08103
Taku Kudo. Subword regularization: Improving neural network translation models with multiple subword candidates. In Iryna Gurevych and Yusuke Miyao (eds.), Proceedings of the 56th Annual Meefing of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 66-75, Melbourne, Australia, July 2018. Association for Computational Lin- /v /P18- 1007 URL httph:tp///// httt:s://ccaattooloo.org/////// or1
guistics. doi:
Taku Kudo and John Richardson. SentencePiece: A simple and language independent subword tokenizer and detokenizer for neural text processing. In Eduardo Blanco and Wei Lu (eds.), Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pp. 66-71, Brussels, Belgium, November 2018. Association for Computational Linguistics. doi: (011663//1/DD8--012 URL
2012/
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, and lon Stoica. Efficient memory management for large language model serving with pagedattention. In Proceedings of the ACM SIGOPS 29th Symposium on Operating Systems Principles, 2023.
J. Lambek. From word to sentence: a pregroup analysis of the object pronoun who(m). Journal of Logic, Language and Information, 303-33333 February 2007. ISSN 1572-9583, doi: 10.1007 (0/1007/s10820 110-849900000005---0 |RL/htp:: //dx. http://wxxddoo.or//////// 1007/s 10011000000071118--00---90--
Joachim Lambek. Type grammar revisited. In Selected Papers from the Second International Conference on Logical Aspects of Compulational Linguistics, LACL 197, pp. 1-27, Berlin, Hei- delberg, 1997. Springer-Verlle
ISBN 3540657517.
Sander Land and Max Bartolo. Fishing for magikarp: Automatically detecting under- trained tokens in large language models. In Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen (eds.), Proceedings of the 2024 Conference on Empirical Methods in Natu- ral Language Processing, pp. 11631-11644, Miami, Florida, USA, November 2024. Asso- ciation for Computational Linguistics. doi: 10.18653 v1 1005553/v1222..eer/ 22224.emmllmmain....
URL
https::/acclantholoyy.ooo org/202 wtt.:24..mnllmmaaam... www.p-main..eeee 649/
15

---

Published as a conference paper at COLM 2024
Yuanzhi Li, Sébastien Bubeck, Ronen Eldan, Allie Del Giorno, Suriya Gunasekar, and Yin Tat Lee. Textbooks are all you need ii: phi-1.5 technical report, 2023. URL
https: http://axxvvv..g/abbbee 2309005633
Jindřich Libovický, Helmut Schmid, and Alexander Fraser. Why don't people use character-level machine translation? In Smaranda Muresan, Preslav Nakov, and Aline Villavicencio (eds.), Findings of the Association for Computational Linguistics: ACL 2022, pp. 2470-2485, Dublin, Ireland, May 2022. Association for Computational Linguis- fics. doi: 10.18653/ 100555/v12000/ w1/2022.22222 fi0.2..innings-acl.119 URL https://aallanthologg) wwrpe/..rrg/2/2//// findings-acl. 194/
Tomasz Limisiewicz, Terra Blevins, Hila Gonen, Orevaoghene Ahia, and Luke Zettlemoyer. MYTE: drrvn byte encoding for better and fairer multilingual language modeling. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar (eds.), Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Pa- pers), pp. 15059-15076, Bangkok, Thailand, August 2024. Association for Computational Linguistics. doi: 10.18653/ vv /22202.acllloogg 804. URL https::/aclaatthht acl-long 8047
M. Lothaire (ed.). Combinatorics on Words. Cambridge University Press, 1997. ISBN 9780511566097.
doi: 10.0077/cho9800515566999 URL http://dx.do1/ ttt.//xx.ooo..oooo wtt.:/doo.orr/11.1000090
(B097805115669)
João Loula, Benjamin LeBrun, Li Du, Ben Lipkin, Clemente Pasti, Gabriel Grand, Tianyu Liu, Yahya Emara, Marjorie Freedman, Jason Eisner, Ryan Cotterell, Vikash Mansinghka, Alexander K. Lew, Tim Vieira, and Timothy J. O'Donnell. Syntactic and semantic con- trol of large language models via sequential monte carlo. In The Thirteenth International Conference on Learning Representations, 2025. URL /tttp:://ppereview. wwtp://eeffoormmte... >xoXn62F2D@
Thomas Mesnard, Cassidy Hardin, Robert Dadashi, Surya Bhupatiraju, Shreya Pathak, Laurent Sifre, Morgane Rivière, Mihir Sanjay Kale, Juliette Love, Pouya Tafti, et al. Gemma: Open models based gemini research and technology, 2024. URL https:
//arxiv.org/abs/// 08295
Microsoft, Abdelrahman Abouelenin, Atabak Ashfaq, Adam Atkinson, Hany Awadalla, Nguyen Bach, Jianmin Bao, Alon Benhaim, Martin Cai, Vishrav Chaudhary, et al. Phi-4- mini technical report: Compact yet powerful multimodal language models via mixture- of-loras, 2025. URL https:://axxiv.org/abb/.
01743
Sabrina J. Mielke, Zaid Alyafeai, Elizabeth Salesky, Colin Raffel, Manan Dey, Matthias Gallé, Arun Raja, Chenglei Si, Wilson Lee, Benoît Sagot, and Samson Tan. Between words and characters: A brief history of open-vocabulary modeling and tokenization in nlp, 2021. URL
10508
Leonardo de Moura and Sebastian Ullrich. The lean 4 theorem prover and programming language. In Automated Deduction CADE 28: 28th International Conference on Automated Deduction, Virtual Event, July 12-15, 2021, Proceedings, pp. 625-635, Berlin, Heidelberg, 2021. Verlla, ISBN 978-3-030--99875-8 doi: 10.1007
URL
Erik Nijkamp, Hiroaki Hayashi, Caiming Xiong, Silvio Savarese, and Yingbo Zhou. Code- gen2: Lessons for training llms on programming and natural languages, 2023a. URL
http:///axxv..ogaaaaa/ 2a0b/ 20..0320520222 02309
Erik Nijkamp, Bo Pang, Hiroaki Hayashi, Lifu Tu, Huan Wang, Yingbo Zhou, Silvio Savarese, and Caiming Xiong. Codegen: An open large language model for code with multi-turn program synthesis, 2023b. URL http:/tt/ttttii...t/r
https///arkw.oor//////2288 wtw.orggg/a...aa//eree 13474
OpenAL. tiktoken. GitHub Repository, 2025.
16

---

Published as a conference paper at COLM 2024
OpenAI, Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, llge Akkaya, Flo- rencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anad- kat, et al. Gpt-4 technical report, 2024. URL htttpss://aaw...orr///aaaa
08774
Artidoro Pagnoni, Ram Pasunuru, Pedro Rodriguez, John Nguyen, Benjamin Muller, Mar- garet Li, Chunting Zhou, Lili Yu, Jason Weston, Luke Zettlemoyer, Gargi Ghosh, Mike Lewis, Ari Holtzman, and Srinivasan Iyer. Byte latent transformer: Patches scale better than tokens, 2024. URL
David D. Palmer. Tokenization and Sentence Segmentation, chapter 2. Marcel Drekker, 2000.
Aleksandar Petrov, Emanuele La Malfa, Philip H.S. Torr, and Adel Bibi. Language model tokenizers introduce unfairness between languages. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS '3, Red Hook, NY, USA, 2023. Curran Associates Inc.
Gabriel Poesia, Oleksandr Polozov, Vu Le, Ashish Tiwari, Gustavo Soares, Christopher Meek, and Sumit Gulwani. Synchromesh: Reliable code generation from pre-trained language models, 2022.
11227
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and llya Sutskever. Language models are unsupervised multitask learners. Technical report, OpenAl, 2019. URL Unssupervised_mmllittsss_eeerre
Abrar Rahman, Garry Bowlin, Binit Mohanty, and Sean McGunigal. Towards linguistically- aware and languuage-nndepeedeent tokenization for large language models (Ilms), 2024. JulL/tttss///arvv.or//////////
033668
Phillip Rust, Jonas F. Lotz, Emanuele Bugliarello, Elizabeth Salesky, Miryam de Lhoneux, and Desmond Elliott. Language modelling with pixels. In The Eleventh International Conference on Learning Representations, 2023. URL http://ppenreiiee.nttffrroommm FkSp8Vw8RjH)
Jacques Sakarovitch. Elements of Automata Theory. Cambridge University Press, October 2009. ISBN 9781139195218. doi: 10.1077/cb9981133992211 URL h/dp::/dxx.... doi /rggg 10. 10111////0997811311952111
Elizabeth Salesky, David Etter, and Matt Post. Robust open-vocabulary translation from visual text representations. In FranciFr Moens, Xuanjing Huang, Lucia Specia, and Scott Wen-tau Yih (eds.), Proceedings of the 2021 Conference on Empirical Methodd in Natural Language Processing, pp. 7235-7252, Online and Punta Cana, Dominican Repub- lic, November 2021. Association for Computational Linguistics. doi: 10. (0.11863//0 118866611///// /2221 emnlp-main.577 URL RRLLhttpss//acaaatholoos wwtp///..orr//220/ www..rr//.......mmm.a.......
emnlp-main. 576/
Craig W Schmidt, Varshini Reddy, Haoran Zhang, Alec Alameddine, Omri Uzan, Yuval Pinter, and Chris Tanner. Tokenization is more than compression. In Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen (eds.), Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pp. 678-702, Miami, Florida, USA, November 2024. Association for Computational Linguistics. doi: URL htt_htttss///aaantolllyye. org/ -ttp://2222eemmmmmmaaaammm
Torsten Scholak, Nathan Schucher, and Dzmitry Bahdanau. Picard: Parsing incrementally for constrained ruto-regressive decoding from language models, 2021. URL https://
arxiv.org/abs/21es 0001/
Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural machine translation of rare words with subword units. In Katrin Erk and Noah A. Smith (eds.), Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1715-1725, Berlin, Germany, August 2016. Association for Computational Linguistics. doi:
URL htt.h: htt.lttsss//claaatoooyoooo//p-/p
17

---

Published as a conference paper at COLM 2024
Joel Spolsky. The law of leaky abstractions. Joel on Software, 2002. wttp:wwww...o../aae.e...aaoeeete cwm/
URL https://www.
joelonsoftware tware.
Stability-AI. Stable Im. GitHub Repository.
URL
stableLM/
Tarun Suresh, Debangshu Banerjee, Shubham Ugare, Sasa Misailovic, and Gagandeep Singh. Dingo: Constrained inference for diffusion llms, 2025. URL https://arxiv org/ abs/2505.2300
Yi Tay, Vinh Q. Tran, Sebastian Ruder, Jai Gupta, Hyung Won Chung, Dara Bahri, Zhen Qin, Simon Baumgartner, Cong Yu, and Donald Metzler. Charformer: Fast character transformers via gradient-based subword tokenization, 2022. URL https://rrxi org/ abs/2106. 12672
Team OLMo, Pete Walsh, Luca Soldaini, Dirk Groeneveld, Kyle Lo, Shane Arora, Akshita Bhagia, Yuling Gu, Shengyi Huang, Matt Jordan, Nathan Lambert, Dustin Schwenk, Oyvind Tafjord, Taira Anderson, David Atkinson, Faeze Brahman, Christopher Clark, Pradeep Dasigi, Nouha Dziri, Michal Guerquin, Hamish Ivison, Pang Wei Koh, Ji- acheng Liu, Saumya Malik, William Merrill, Lester James V. Miranda, Jacob Morrison, Tyler Murray, Crystal Nam, Valentina Pyatkin, Aman Rangapur, Michael Schmitz, Sam Skjonsberg, David Wadden, Christopher Wilhelm, Michael Wilson, Luke Zettlemoyer, Ali Farhadi, Noah A. Smith, and Hannaneh Hajishirzi. olmo 2 furious, 2025. URL https://arxiv.orgg hwrg/abs/220....
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. Llama: Open and efficient foundation language models, 2023a. URL httpp:://aarii..rrr/bbb//////
13971
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schel- ten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, lliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. Llama 2: Open foundation and 200.b/////07009088888
fine-tuned chat models, 2023b. URL
Shubham Ugare, Rohan Gumaste, Tarun Suresh, Gagandeep Singh, and Sasa Misailovic. Itergen: Iterative semantic-aware structured LLM generation with backtracking. In The Thirteenth International Conference Learning Representations, 2025a. URL https:
Shubham Ugare, Tarun Suresh, Hangoo Kang, Sasa Misailovic, and Gagandeep Singh. Syn- code: LLM generation with grammar augmentation. Transactions on Machine Learning Research, 2025b. ISSN 2835-8856. URL httpt:::/pppeeeeiieeeeeee///
Unicode Technical Committee. Unicode standard. Standard, Unicode, Inc., 2025. URL
https://www.un unwcwde.eccceeecmm org//versions/ltess//
Hendrik van Antwerpen and Alexander Neubeck. bpe readme. GitHub, 2024. URL https: wwwp.tt........uo....ct htt.i///iiictcitoo/////e/////e/n
.md.
Anne van Kesteren. Encoding. Standard, WHATWG, 2024. URL
whatwg.org
18

---

Published as a conference paper at COLM 2024
W3Techs. Usage statistics of character encodings for websites. Q-Success 02 2025. URL
Brandon T. Willard and Rémi Louf. Efficient guided generation for large language models,
2023. |hthtts::///arxi http:///axxiv..ogabbbboo/ wrg.:or//////////// 09702
Linting Xue, Aditya Barua, Noah Constant, Rami Al-Rfou, Sharan Narang, Mihir Kale, Adam Roberts, and Colin Raffel. Byt5: Towards a token-free future with pre-trained byte-to-byte models. Transactions of the Association for Computational Linguistics, 10:291- 306, 03 2022. ISSN 2307-387X. doi: 10.1162/tacl aat/atac_aaaaaaa __0661. URL 1162/tacl a 00461
An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, Chujie Zheng, Dayiheng Liu, Fan Zhou, Fei Huang, Feng Hu, Hao Ge, Haoran Wei, Huan Lin, Jialong Tang, Jian Yang, Jianhong Tu, Jianwei Zhang, Jianxin Yang, Jiaxi Yang, Jing Zhou, Jingren Zhou, Junyang Lin, Kai Dang, Keqin Bao, Kexin Yang, Le Yu, Lianghao Deng, Mei Li, Mingfeng Xue, Mingze Li, Pei Zhang, Peng Wang, Qin Zhu, Rui Men, Ruize Gao, Shixuan Liu, Shuang Luo, Tianhao Li, Tianyi Tang, Wenbiao Yin, Xingzhang Ren, Xinyu Wang, Xinyu Zhang, Xuancheng Ren, Yang Fan, Yang Su, Yichang Zhang, Yinger Zhang, Yu Wan, Yugiong Liu, Zekun Wang, Zeyu Cui, Zhenru Zhang, Zhipeng Zhou, and Zihan Qiu. Qwenã technical report, 2025a. (RL/httss://axxi www.voorg/aaooo org/abs/2255 2505. 09388
An Yang, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang, Haoran Wei, Huan Lin, Jian Yang, Jianhong Tu, Jianwei Zhang, Jianxin Yang. Jiaxi Yang, Jingren Zhou, Junyang Lin, Kai Dang, Keming Lu, Keqin Bao, Kexin Yang, Le Yu, Mei Li, Mingfeng Xue, Pei Zhang, Qin Zhu, Rui Men, Runji Lin, Tianhao Li, Tianyi Tang, Tingyu Xia, Xingzhang Ren, Xuancheng Ren, Yang Fan, Yang Su, Yichang Zhang, Yu Wan, Yuqiong Liu, Zeyu Cui, Zhenru Zhang, and Zihan Qiu. Qwen2.5 technical report, 2025b. URL http://axww...rraas///2.....
Zhixuan Yang and Nicolas Wu. Modular models of monoids with operations. Proc. ACM Program, Lang., 7(ICFP), August 2023. doi: 10.1145/3607850. URL http:://////oo.rr//11
1145/3607850
Yard1. Use tgi-like incremental detokenization. GitHub Pull Request, 2023. URL https: //gtthb..com httpm///wwmmmmmooee////////////a
Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Chuyue Sun, Jeff Huang, Cody Hao Yu,
Shiyi Cao, Christos Kozyrakis, Ion Stoica, Joseph E. Gonzalez, Clark Barrett, and Ying Sheng. Sglang: Efficient execution of structured language model programs, 2024. URL http:///arkw..rrr/as/222222 07104
Vilém Zouhar, Clara Meister, Juan Gastaldi, Du, Mrinmaya Sachan, and Ryan Cot- terell. Tokenization and the noiseless channel. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.), Proceedings of the 6lst Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), Pp. 5184-5207, Toronto, Canada, July 2023a. Association for Computational Linguistics. doi: 10.18653/vi /111///22222l/1oog 284. URL htttp:://aclannhollog/ orrg///g///33333 acl- long. 284/
Vilém Zouhar, Clara Meister, Juan Gastaldi, Li Du, Tim Vieira, Mrinmaya Sachan, and Ryan Cotterell. A formal perspective on byte-pair encoding. In Anna Rogers, Jor- dan Boyd-Graber, and Naoaki Okazaki (eds.), Findings of the Association for Compu- iational Linguistics: ACL 2023, pp. 598-614, Toronto, Canada, July 2023b. Association for Computational Linguistics. doi: 10.18653 http://////...mmgggad......33. //aclantholloyyorgg//// findings-acl.3s
findings-acl.3.. URL https:
19

---

Published as a conference paper at COLM 2024
A Extended related work
Tokenization notation and terminology. The process we call "cutting" is standard step
in tokenization but is represented variously in the literature. Sennrich et al. (2016) use
or a space; Gastaldi al. (2024) use (); Schmidtt et al. (2024) Bostrom Durrett (2020)
use a space; Koo et al. (2024) use ( (2018) uses (7) Kudo & Richardson (2018) wrap
tokens with square brackets; Cognetta & Okazaki (2024) use ; and Geng et al. (0024) use
color to distinguish tokens. We tollow [ & van der Merwe (2023) in using (?),
though we extend their notation by requiring that cut sequences begin and end with (?).
Morphisms in tokemization. We use the term homomorphism the way Geng et al. (2024)
use it. For [Sakarovicch (2009), homomorphism is bijective morphism. Gastaldi et al. (2024) call multiplicatiie what we refer to as a homomorphism; with the following addi- tional constraint that it map non-empty sequences to non-empty sequences, it also has trivial kernel: f + x(0) o eg. Lothaire (1997) and Sakarovitch (2009) call morphism what we call a homomorphism with the additional requirement that it map the identity member to the identity member: x(Ea) = ey. We include neither of these additional re- strictions because they are not necessary for our work here.
Subword tokenization methods. A cutting tokenizer like ours is generalization of a sub- word tokenizer (Sennrich et al., 2016 Kudo, 2018 Kudo Richardson 2018). The perfor- mance of subword tokenizers is contested. The reader is directed inter alia to Gallé (2019); Zouhar et al. 2023a) for favorable impression and Bostrom & Durrett (0020); Schmidt et al. (2024) Chai et al. (2024a) for negative one. Practically representing the negative camp, tokenizer-free models work directly on input characters (e.g. Tay et al., 2022 Clark
al. 2022), bytes (e.g. Xue et al. 2022; Pagnoni et al. 2024), or on images of input text (e.g.
Salesky et al. 2021 Rust et al. 2023 Chai et al. 2024b).
Byte-level and character-level approaches. Byte-pair encoding has been studied exten- [Bostrom BivelyyBostrom & Durrett (2020) argue that Unigram is superior to BPE, Gallé (2019) argue that performs highly because it compresses the input, SuttSchmiiteeeee et al. (0244) perform experiments that suggest that compression is not necessary or sufficient for pertormance in tokenizer. Zouhar et al. (2023a) propose an information theoretic standard, Rényi entropy, for why certain tokenizers perform better than others: Cognetta et al. (2024) supply counter
examples to the argument of Zouhar al. (2023a). Libovicky et al. (2022) examine the ef-
ficacy of tokenizationless character-level machine translation compared to character-level BPE and find that the former performs best only as well the latter.
Inter-language performance comparisons. Limisiewicz et al. ); Hofmann et al. (2022) examine adapting subword tokenization to respect morphological boundaries in language in order to improve performance in non-European languages. Petrov et al. (2023) Ahia et al. (2023) show that byte-level and character-level tokenization introduce severe dis- crepancies among languages, due in part to the varying lengths of byte sequences used to represent text in various languages.
B Details about UTF-8
Table 4: UTF-8 bit distribution, showing how to convert code points, represented as binary numbers, into the bytes of UTF-8. (Unicode Technical Committee 2025 Table 3-6).
Code Point
First Byte
Second Byte
Third Byte
Fourth Byte
00000000 XXXXXXXX 00000yyy уУXXXXX zzzzyyyy ууXXXXXX 000muuuu ZZzZyyyy ууXXXXX
XxxxxXXX 110yyyyy
10xxxxxx
1110zZZZ
10yyyyyy
10xxxxxx 10yyyyyy
11110uuu
10uuzzzz
10xxXXX
In the main body of the paper we ignore the concept of code points entirely and exclusively treat UTF-8 code units. However, in Appendix D we discuss hack to store byte-level
20

---

Published as a conference paper at COLM 2024
tokens in well-formed UTF-8 files; will need to discuss code points such there. Each character in Unicode (Unicode Technical Committee 2025) is mapped to a number the range to 10FFFF16 called code point. To turn code point into its UTF-8 code unit, convert the code point to bytes as shown in Table 4 process that interprets UTF-8 bytes as characters, process waved away in the body of the paper, must disassemble the bytes it receives on its input to recover the code point of the character it must display.
Several properties of UTF-8 referenced in the main text immediately obvious by visual inspection of Tables 4 and 1 For example, any sequence made up exclusively of bytes starting 10, that is, in the range 80..B, can never be well-formed UTF-8. Similarly, no sequence made up exclusively of bytes beginning with 110, 1110, or 11110 can ever contain any well-formed encoded forms. Also, the bytes CO-C1 and F5-FF never appear in UTF-8 at all, so they can also be used to disrupt well-formed encoding forms.
Note also that not all characters are encoded by the same number of bytes. In tokenizers based on merging pairs of tokens, the number of bytes that make up a character could influence the likelihood that that character is represented by more than one token. We leave verifying or disproving this conjecture to future work.
C Python implementation of Algorithm 1
Listing Implementation of Algorithm 1 from the serving engines discussed in Section assigned the value ?.. Note that the variables call and j are named prefix_offset and cea__offet respectively. The fast version of the Hugging Face cokenizers library uses a Rust translation of this logic (Hug- gingface 2025).
In the real listing, the variable replacement_coe
def decode_token( self,
3
all_input_idss List[int],
4
prefix_offset. int =
read_offset: int = 8,
skip_special_tokens: bool False, Tuple[str, int, int]:
prefix_text self tokenizer decode
9
new_textto self tel..tttkenizzerddccde sul__inpttiddsppefiix.fffff [kkpssppciaaloooke==sspppppppeee
13
14
len (enew_teex) len(prefix_text not new_text
theh endwsitthhcrppllacenttt.ccaa) new_text nww_teet mew..text(len(prfixx.eee :]
18
return new_text, read_offset, len(all_inutt_ids)
else: return "" prefix_offset, read_offset
Table gives example of incrementally decoding sequence of byte tokens. The first col- umn of the execution trace contains the byte tokens to be detokenized, read order from top to bottom. The second column shows the characters emitted they completed. The third and fourth columns show the values of and as they are advanced through the sequence of byte tokens.
21

---

Published as a conference paper at COLM 2024
Table 5: Trace of executing Algorithm 1
on the tokens from Example
Byte token
Text emitted
i
RE A4
285
अ
(O A42
0
2
1971
2
4
2O A5 8D EO A4
4
AA8
4
6
EO A4 BF EO A42
4
6
AEE
6
8
RO A5 802
8
9
EO A4
BB3
T5
11
EO A5 872
11
12
D Mapping bytes to Unicode and back
r
p
a
π
r
P
a
π
И
JI
a
(D093 DD ING
(D180
DOBO
DOB4:
(20 DOB3I (D180
DOBO D
DOB41 D'
(DOB8 ID,
DOBB
DOBO D
D
D' 1G DP iNG
Do
Table 6: The first two words of The Building of Skadar (Serbian: Зилане Cкаара), paa иpaaиna", transliterated "Grad gradila" ("The city was built"). The top row is the quence of characters making up these words, the middle row is the sequence of bytes that are the UTF-8 encoding of this sequence of code points, and the bottom row is the bytes of the middle row mapped to characters according to the mapping defined in Listing 2 The squiggles 2 in the bottom two rows indicate the tokenization according Qwen3's vocabulary Yang et al. 2025a)
Listing Code from GPT-2 [Radford al. 2019) that defines an injective but not surjective mapping between the set of natural numbers from 0 to 255 and the set of natural numbers. AC16, AE ... FF16 are mapped to themselves. The remaining numbers are mapped in order to 100,, through 143 The returned dictionary maps from ints representing byte values to strs of one character representing code points.
The numbers 26 .. A1
def bytes_to__uiiee to_unicode())
bs
3
(ist(range ord("=") 1))
4
1ist (range (ord("i") ord(">") + 1)) (ranger (ord("e ("e"), ord(""") + 1))
5
)
bs[:]
8
n
9
for b in range (2+*))
if b not in bs: bs. (b)
append n)
13
+=
14
cs [chr for in cs]
return dict(zip(bs, cs))
Hugging Face distributes tokenizer vocabularies as UTF-S-encoded files. Since program- mers tend to work with UTF-S-encoded strings rather than directly with byte sequences,
II HpTP-speak: content-type text/plain; charset=UTF-8
22

---

Published as a conference paper at COLM 2024
it is convenient to be able to represent arbitrary byte sequences, such those produced by arbitrarily clumping bytes, UTF-8 sequences. P GPT-2 (Radford et al. 2019), because had a byte-level vocabulary stored in UTF-8 files, introduced a mapping between each byte and a code point (see B and storing the code points as UTF-8 byte sequences. The tokenizer's 's implementation must convert back and forth between the code points and the bytes they represent interact with byte-level inputs.
giss Python procedure for mapping from bytes to (printable) code points. Most of the code points between 0016 and FF16 are printable characters, so though the result will be an ugly mix of semantically insignificant characters, the result will be made up entirely of printable characters. The characters in the range 0016 through FF16 that are control or whitespace characters are mapped to the code points beginning at 100 Luckily the entire block U+0100-U+1700 is printable characters. The transition between the middle and bottom rows of Example exemplifies these transformations.
E Unicode character handling SynCode evaluation prompt and grammar
As discussed in Section to evaluate SynCode's s ability to handle non-ASCII Unicode char- acters, we conducted an experiment using emoji generation task. We selected a subset of the TweetEval emoji dataset Barbieri al. (2020), filtering for three common emoji classes. The task required the model to generate exactly one emoji character in response to given tweet, adhering to a constrained grammar specification. This evaluation directly tested SynCode's s handling of multi-byte UTF-8 sequences, which was limitation in earlier ver- sions.
Listing 3 Grammar specification for emoji generation task using Unicode escape se- quences.
// Lark grarmar to validate single emoji output start: emoji
// Define the emojis from the TweetEval emoji dataset emoji: "XU0001F60D" "XU0001F602" "XU0001F609"
emoji:
The prompt template instructed the model to analyze tweets and respond with exactly one emoji from the allowed set (Listing 4 We evaluated this task across 100 examples from the TweetEval test set on two versions of SynCode: v0.2.0 which used character-level finite state machine (FSM), and the current version which implements byte-level FSM with our recommended fix.
The results demonstrated significant improvement in Unicode handling capability. Syn- Code v0.2.0 with its character-level FSM failed all 100 examples, resulting in 100% crash rate and 0% accuracy. In comparison, the current implementation after suggested fix processed all examples without crashes, achieving 62% accuracy in emoji prediction.
A notable exception is OpenAT, who after GPT-2 have worked directly with byte sequences that not guaranteed be valid UTF-8.
23

---

Published as a conference paper at COLM 2024
Listing Prompt template for emoji generation task (emoji symbols represented as place- holders)
You are evaluating tweets to assign the most appropriate emoji.
INSTRUCTIONS:
1. Read the tweet below carefully.
2. Select the SINGLE most appropriate emoji that captures the sentiment.
3. Respond with ONLY that emoji no words or other characters.
The emoji must be one of the 3 valid options from this set:
Tweet:
"tweet_text"
Your response:
24


Reviews:
[{"review_id": "x8U9bL4c1L", "reviewer": "Reviewer_cvmT", "summary": "The main thesis of this paper is that two tokenized sequences, detokenize to the same output whether combined or detokenized separately. The authors formalise BPE tokenization to prove that most modern byte-level tokenizers break this morphism assumption, and therefore can generate invalid UTF8 sequences during decoding. The authors propose a simple mitigation algorithm (Algorithm 1) to solve token-level decoding to UTF8 by queueing byte level tokens until a valid UTF8 character is formed. They show that this fix, already implemented in most major serving engines, works on a toy problem of emoji decoding when compared to eagerly naively decoding tokens to UTF8. The authors also do some analysis on broader tokenizers to categorise them into byte-level (huggingface and others) or character-level (sentencepiece).", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "- The morphism property that the authors outline is a relevant and interesting point to raise when thinking and designing tokenizers, and has downstream consquence in broader LLM inference (for instance when streaming the tokens of a model directly to UTF8).\n- The authors provide mathematical proofs to formalise the problem of current byte-level tokenization\n- The authors motivate the implementation of Algorithm 1 which is already present in several LLM inference libraries\n- The paper is well written and clear", "reasons_to_reject": "- 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.\n- The algorithm 1 that the authors propose has already been implemented by various different open-source implementations and is therefore not entirely novel. Additionally, as the authors themselves also note, this algorithm does not provide guarantees that the decoding process will lead to valid UTF8 and only solves the problem for common issues. Ultimately, this paper provides theoretical and empirical background for an engineering trick that has already been implemented by different sources.", "questions_to_authors": "Apologies for the lack of line numbers, I'm not sure why, but but they were not present in your submission. \n\nThe 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? One could mask out tokens with potential to create invalid sequences and thus expand Algorithm 1 further to entirely guarantee only valid UTF8 during decoding.\n\nYou note that ablations on tokenizers are seldom performed but some previous work in multilingual (Liang et al., 2023) and code generation (Dagan et al., 2024) have done ablations at small scale -- though more looking at tokenizers from the perspective of compression. \n\nTypos/Grammar: \"tokeniation\" -> \"tokenization\"; \"vocabluary\" -> \"vocabulary\";  \"return the same cutting for a given input: pace Gastaldi et al..\"\n\nReferences:\n\nDavis Liang, Hila Gonen, Yuning Mao, Rui Hou, Naman Goyal, Marjan Ghazvininejad, Luke Zettlemoyer, and Madian Khabsa. 2023. XLM-V: Overcoming the Vocabulary Bottleneck in Multilingual Masked Language Models. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 13142–13152, Singapore. Association for Computational Linguistics.\n\nGautier Dagan, Gabriel Synnaeve, and Baptiste Rozière. 2024. Getting the most out of your tokenizer for pre-training and domain adaptation. In Proceedings of the 41st International Conference on Machine Learning (ICML'24), Vol. 235. JMLR.org, Article 387, 9784–9805.", "extra_scores": {}}, {"review_id": "WMq5uhZwik", "reviewer": "Reviewer_Vin2", "summary": "This paper notices the problem of UTF-8 detokenization when using byte-level tokenizers. Essentially, it shows that any byte-level tokenizers that may lead to invalid UTF-8 tokens can be potentially leaky and produce discrepancy when comparing results for two raw byte strings produced by different orders of concatenating and detokenization. The paper formalizes this using monoid theory and shows that any vocabulary that can lead to invalid UTF-8 tokens has this problem. The paper finally tries to mitigate this problem by introducing an incremental detokenization algorithm. A detailed case study is also conducted to show the practicality of the problem.", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "- The paper uses Monoid to formalize the problem and rigorously proves all the results\n- The case study of the paper is extensive and coveres majority of tokenizers used in popular models", "reasons_to_reject": "- The problem itself is fairly simple and highly restrictive. The paper also acknowledges this in the case study that many of the current tokenizers have already taken this into account.\n- The paper formalizes the problem with the Monoid theory but made little to none theoretical contributions regarding nontrivial results or novel techniques.\n- The solution proposed in this paper is the standard incremental decoding algorithm, which is not novel at all.\n- 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.", "questions_to_authors": "- Why are Monoids necessary for illustrating the problem? Are there more straightforward approaches to show the existence of the problem?\n- What are the differences between the algorithm proposed and the incremental decoding algorithm that are implemented in, say, Python? \n- How are other constraint decoding schemes affected by this problem?\n- 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?", "extra_scores": {}}, {"review_id": "YVRvFHlSmn", "reviewer": "Reviewer_x3kb", "summary": "This paper formalizes the non-morphism issue of detokenization in systems based on byte-level detokenization. It uses a formalism based on monoids and stochastic maps which formally concludes an impossibility which can be used to explain  issues in incremental detokenization, a problem prevalent in modern streaming services based on language models.\nThe authors propose a potential solution to this issue using an algorithm which incrementally detokenizes tokens as long as they are well-formed UTF-8 and otherwise \"collects\" tokens until they form a well-formed one, together with the previous ones collected. While this algorithm introduces other issues (e.g., unlimited memory costs), it nevertheless provides a simple approach to overcome detokenization issues encountered in current systems. This is highlighted with a concrete case study.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "- formalization of detokenization issues encountered in byte-level tokenizers which are used by many state-of-the-art language models\n- algorithm on how to deal with issues encountered during incremental detokenization (albeit not feasible for pruduction systems due to unlimited memory costs)\n- the paper follows a clear structure and is mostly well-written", "reasons_to_reject": "- some more examples are needed along the formalized theoretical framework which helps the reader to better understand the formal definitions\n- 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)", "questions_to_authors": "- I suggest to shortly explain the term \"monoid\" if you use it in the Introduction section\n- The transition from the explanatory example for decoding issues (Table 1) to stating the contributions can be improved, there should be a clear motivation explaining your work/contributions given the issues discussed before.\n- What do you exactly refer to with \"cell\" in the text explaining Table 1?\n- Can you clarify the difference between monoid sum^{star} and sum^{star_squiggle_circle_star} in Definition 7?\n- 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.\n- In Algorithm 1, what is epsilon? How do you deal with an increasing buffer which does never see a well-formed UTF8 sequence?", "extra_scores": {}}, {"review_id": "ylN3GXvQ1x", "reviewer": "Reviewer_MUTr", "summary": "This paper investigates a subtle but critical issue in language model tokenization: how subword tokenizers, particularly byte-level ones, can violate UTF-8 validity and morphism properties when detokenizing outputs. Using a rigorous algebraic formalism based on monoids, the authors derive a fundamental impossibility result: no byte-level tokenizer with a finite vocabulary can simultaneously guarantee UTF-8 validity and full coverage of Unicode inputs. The authors introduce a theoretical framework that explains how incremental detokenization and streaming decoding break when using byte-level tokenization. They propose Algorithm 1 as a partial solution, evaluate it on real-world systems (SynCode, HuggingFace TGI, vLLM), and demonstrate bug fixes guided by the theory. The paper also categorizes tokenizers used by major foundation models and discusses implications for model serving, constrained generation, and Unicode safety.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. Tackles a foundational systems issue underlying nearly all LMs. \n2. Presents novel formal results on tokenization morphisms using monoid theory. Derives rigorous proofs that relate tokenizer vocabulary composition to UTF-8 correctness.\n3. Demonstrates how theoretical results predict real bugs in existing model infrastructure. Offers a practical solution (Algorithm 1), with empirical validation on SynCode and inference engines.\n4. Provides a compelling mix of formal theory, practical systems analysis, and engineering recommendations.", "reasons_to_reject": "1. Heavy reliance on abstract algebraic notation and formal language theory (monoids, morphisms) may limit accessibility for practitioners. It is difficult to follow the paper. \n2. Algorithm 1 is presented as a workaround, not a fundamental fix—it avoids errors but introduces unbounded memory risk. The mitigation strategies are not fully benchmarked in terms of latency or robustness across model sizes.\n3. While the theoretical analysis is excellent, the paper stops short of offering new tokenizer designs that inherently satisfy morphism and UTF-8 constraints.", "questions_to_authors": "1.  Could your impossibility theorem be extended to cover other encodings (e.g., UTF-16, UTF-32) or only applies to UTF-8?\n2. Have you observed model output behavior (e.g., hallucinations, truncation) that can be directly attributed to UTF-8 detokenization errors?\n3. Could an embedding-level mitigation be proposed—e.g., enforcing character-level constraints during decoding without restricting the tokenizer vocabulary?\n4. How does Algorithm 1 affect streaming performance in real deployments? Are memory buffers manageable at inference scale?", "extra_scores": {}}, {"review_id": "R2HEgNT7ll", "reviewer": "Reviewer_KwbY", "summary": "This paper formalizes subword tokenization and treats issues that arise when converting back and forth between bytes and unicode.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The general formal approach is quite nice and the *morphism* requirement is a nice one. It's not clear what the value of adding the stochastic dimension is. It doesn't play any role here.\n\nThe homomorphism proof seems solid but would be easier to follow if homomorphism were actually defined explicitly.\n\nThe 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*?\n\nI was suprised to see no explicit contact with the finite-state literature. I think this is more opportunity than problem though.", "reasons_to_reject": "There are a number of undefined items, e.g. serving engine and foundation model.\n\nThe general proposal seems to be: have a buffer. Is this new?\n\nIt 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.", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AVNPhQsnH9", "reviewer": "Reviewer_uy5s", "summary": "This paper provides a proof for the generation of invalid UTF-8 sequences, as a result of the tokenizer vocabulary not covering the full range of Unicode code points. The authors propose an algorithm to prevent errors in UTF-8 decoding. The paper is well organized, but lacks clarity in some key areas. The paper addresses and important issues, but does not make a sufficiently large contribution to the understanding of the issue or make clear steps towards a solution.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "Incomplete and invalid UTF-8 sequences constitute an important issue with tokenization. They cause errors in tokenizations through the sequence and can lead to glitch tokens (https://arxiv.org/pdf/2405.05417), which can lead to unpredictable and unsafe model behavior (https://arxiv.org/pdf/2402.14020).", "reasons_to_reject": "(1) 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). Given the previous work on the topic and the fact that the proposed algorithm is not tested, the proof itself is not a sufficient contribution. \n\n(2) 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. \n\n(3) The use of terminology of the paper is imprecise and the authors introduce novel terms, where there already exist terms. Furthermore, the authors claim that the paper advances terminology on this topic, which I do not agree to be a contribution of the paper. For example, 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. 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. \n\n(4) The authors do not sufficiently engage with the literature on this topic. In some cases, prior work is cited, but the paper does not reflect the findings of the cited work. The most obvious case relates to the claim that “the power of BPE has attained the status of a folk theorem and is taken for granted” (p. 7). However, in the last paragraph of Section 5 (p. 9), the authors cite Bostrom & Durrett (2020) and Gallé (2019) and discuss previous work on the features of BPE that make it effective and widely adopted. I think the authors should add to this and discuss other evidence about the pros and cons of BPE (e.g. https://aclanthology.org/2024.findings-naacl.247.pdf, https://arxiv.org/pdf/2411.08671, https://aclanthology.org/2023.cl-4.5/). I also recommend the authors also look at this discussion of tokenization as lossless (https://arxiv.org/pdf/2309.10668), the definition of partial UTF-8 sequences (https://arxiv.org/pdf/2405.05417), and work on glitch tokens (https://arxiv.org/pdf/2402.14020, https://arxiv.org/pdf/2405.05417). \n\n(5) 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.", "questions_to_authors": "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?\n\nTypos:\n* utf-8 → UTF-8\n* greek → Greek\n* lettter → letter\n* “Gastaldi et al. (2024); Ahia et al. (2023).” (Section 3.1) → use \\citep{}\n* \"Petrov et al. (2023); Ahia et al. (2023)\" (p.8) → use \\citep{}\n* \"Synchromesh Poesia et al. (2022) and SynCode Ugare et al. (2024)\"→  Synchromesh (Poesia et al., 2022) and SynCode (Ugare et al., 2024); use \\citep{}\n* Error with OpenLLM citations (p. 8)\n* langauges → languages\n* smal → small\n* Missing or incorrect \\ref{} in second paragraph of Appendix A\n\nFormatting issues:\n* The ≀ in Table 1 indicate token boundaries, but it difficult to visually dermine byte boundaries. Could the authors add color coding or some other way to aid the reader?\n* The authors didn’t submit the paper in preprint format (with line numbers)", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents a formal proof that byte-level tokenizers with ill-formed UTF-8 tokens can generate invalid UTF-8 sequences, which is an underexplored issue with practical implications in LLM serving and constrained decoding. The use of monoid theory provides a rigorous foundation that sheds light on a fundamental weakness in widely used tokenization pipelines. While the paper's scope is niche and its empirical evaluation limited, as noted by Reviewers Vin2 and uy5s, its contribution lies in surfacing a subtle yet impactful problem that has already manifested in real-world systems. The authors have addressed key reviewer concerns and clarified that their primary aim is to initiate broader discussion, not to propose a fully novel algorithmic solution. The writing could be improved to enhance clarity, particularly for a broader NLP audience unfamiliar with the formalism. Nonetheless, the work is likely to spark valuable discussions during the poster session and may serve as a stepping stone for more robust tokenizer design in future LLM systems. I lean toward acceptance.
Decision: Accept