To handle arbitrary text, emojis, and multilingual inputs without running into out-of-vocabulary errors, modern Large Language Models (LLMs) rely heavily on byte-level tokenization. Instead of mapping tokens strictly to whole words or clean subwords, byte-level Byte-Pair Encoding (BPE) or byte-fallback mechanisms operate directly on raw bytes.
However, as explored by Preston Firestone et al., this design choice introduces a "leaky abstraction." By exposing the underlying byte representation typically hidden by text encoding standards, the tokenizer inadvertently gives the language model the power to manipulate the internal structure of characters. This flexibility comes with a severe side effect: the model can generate sequences of bytes that violate the syntactic rules of UTF-8, producing ill-formed text that breaks downstream applications.
The Anatomy of an Incomplete Token
To understand why this happens, we must look at how UTF-8 encodes text. While standard ASCII characters take up a single byte, many characters (like accented letters, non-Latin scripts, or emojis) require multi-byte sequences consisting of two to four bytes. These sequences must follow strict bit-pattern rules to be considered valid.
When a byte-level tokenizer builds its vocabulary from a corpus, it frequently creates what Eugene Jang et al. define as "incomplete tokens." These are vocabulary items representing byte fragments that do not form a valid Unicode character on their own. Instead, they act as prefixes (ending with stray bytes) or suffixes (beginning with stray bytes) that require adjacent tokens to complete the character.
Because an LLM generates text token-by-token by sampling from a probability distribution, it can easily select an incomplete prefix token and follow it with an incompatible token, or fail to output the necessary suffix entirely. When this happens, the resulting byte stream violates the multi-byte sequence rules of UTF-8, yielding structurally invalid text (Sangwhan Moon et al.).
The Mathematical Flaw of Detokenization
This issue is not merely a training deficiency that disappears with larger models; it is a fundamental algebraic limitation. In two closely related studies, Preston Firestone et al. and Preston Firestone et al. model tokenization using monoid theory. They prove that when using a byte-level tokenizer with a fixed vocabulary, the detokenization process is not a structure-preserving map (a homomorphism).
For tokenization to be perfectly safe, mapping a sequence of tokens back to text should always land within the space of valid UTF-8 strings. However, because the vocabulary contains individual bytes or incomplete fragments, the model can traverse paths in the token space that map directly to invalid regions of the byte space. The authors demonstrate that preventing this completely would require an impractically large vocabulary. Consequently, byte-level tokenizers inherently permit the generation of ill-formed UTF-8 regardless of the model architecture.
Wasted Probability and Unreachable Tokens
Because the model must learn these intricate byte-level constraints purely from data, it faces a steep learning curve. Sangwhan Moon et al. demonstrate that a language model requires twice as much training data to master the structural rules of UTF-8 validity as it does to stabilize its standard perplexity.
This difficulty manifests in two distinct types of vocabulary inefficiencies:
- Noncanonical Sequences: As shown by Tim Vieira et al., models waste a significant amount of probability mass on "noncanonical" token sequences—strings of tokens that decode to valid text but violate the tokenizer's own greedy generation rules. Crucially, the authors note that even if you force a model to follow canonical BPE rules at test time, it still does not guarantee character-level UTF-8 validity.
- Glitch and Unreachable Tokens: Through structural reachability analysis, Sander Land et al. found that many vocabularies contain "glitch tokens"—broken UTF-8 sequences or unreachable BPE fragments that the tokenizer is structurally incapable of producing from standard text. These under-trained tokens remain embedded in the model's weights, creating vulnerabilities where unusual token combinations ("improbable bigrams") can trigger hallucinations or unpredictable behavior (Eugene Jang et al.).
Why Simple Mitigations Fail
When downstream systems encounter these invalid byte streams, they often crash or produce corrupted outputs. Common engineering workarounds fail to fully resolve the underlying issue:
- Replacement Characters: Replacing invalid byte sequences with a placeholder (like the Unicode replacement character ``) acts as a superficial band-aid. It fails to restore the expected mathematical properties of tokenization and can corrupt text semantics (Preston Firestone et al.).
- Incremental Detokenization: Serving engines often attempt to decode bytes incrementally as they are generated to stream text to users. However, Preston Firestone et al. point out that if the model generates a sequence of bytes that never resolves into a valid UTF-8 character, the incremental decoder can suffer from memory leaks or state accumulation bugs as it waits indefinitely for a resolving byte.
Ultimately, these insights reveal that byte-level tokenization trades structural safety for vocabulary flexibility, leaving a critical gap between token-level generation and character-level encoding validity.
Key Foundational Work
UTF-8 Plumbing: Byte-level Tokenizers Unavoidably Enable LLMs to Generate Ill-formed UTF-8 (2025) — contributed 9 concept elements to this direction.
Byte-level Tokenizers Unavoidably Enable LLMs to Generate Ill-formed UTF-8 (2025) — contributed 9 concept elements to this direction.
Language Models over Canonical Byte-Pair Encodings (2025) — contributed 1 concept elements to this direction.