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

arXiv: https://arxiv.org/abs/2511.05578 · HTML: https://mlsanity.com/paper/2511.05578/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 75 references that are in the map.
- First posted on arXiv 5 Nov 2025.

## Builds on (most cited first, 30 of 40)

- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing](https://mlsanity.com/paper/1808.06226/) (2018)
- [Phi-3 Technical Report: A Highly Capable Language Model Locally on Your Phone](https://mlsanity.com/paper/2404.14219/) (2024)
- [CodeGen: An Open Large Language Model for Code with Multi-Turn Program Synthesis](https://mlsanity.com/paper/2203.13474/) (2022)
- [Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates](https://mlsanity.com/paper/1804.10959/) (2018)
- [Phi-4-Mini Technical Report: Compact yet Powerful Multimodal Language Models via Mixture-of-LoRAs](https://mlsanity.com/paper/2503.01743/) (2025)
- [ByT5: Towards a token-free future with pre-trained byte-to-byte models](https://mlsanity.com/paper/2105.13626/) (2021)
- [TweetEval: Unified Benchmark and Comparative Evaluation for Tweet Classification](https://mlsanity.com/paper/2010.12421/) (2020)
- [PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models](https://mlsanity.com/paper/2109.05093/) (2021)
- [CANINE: Pre-training an Efficient Tokenization-Free Encoder for Language Representation](https://mlsanity.com/paper/2103.06874/) (2021)
- [Language Model Tokenizers Introduce Unfairness Between Languages](https://mlsanity.com/paper/2305.15425/) (2023)
- [Efficient Guided Generation for Large Language Models](https://mlsanity.com/paper/2307.09702/) (2023)
- [Byte Pair Encoding is Suboptimal for Language Model Pretraining](https://mlsanity.com/paper/2004.03720/) (2020)
- [Do All Languages Cost the Same? Tokenization in the Era of Commercial Language Models](https://mlsanity.com/paper/2305.13707/) (2023)
- [Charformer: Fast Character Transformers via Gradient-based Subword Tokenization](https://mlsanity.com/paper/2106.12672/) (2021)
- [Synchromesh: Reliable code generation from pre-trained language models](https://mlsanity.com/paper/2201.11227/) (2022)
- [Between words and characters: A Brief History of Open-Vocabulary Modeling and Tokenization in NLP](https://mlsanity.com/paper/2112.10508/) (2021)
- [Tokenizer Choice For LLM Training: Negligible or Crucial?](https://mlsanity.com/paper/2310.08754/) (2023)
- [Coercing LLMs to do and reveal (almost) anything](https://mlsanity.com/paper/2402.14020/) (2024)
- [Tokenization Is More Than Compression](https://mlsanity.com/paper/2402.18376/) (2024)
- [SynCode: LLM Generation with Grammar Augmentation](https://mlsanity.com/paper/2403.01632/) (2024)
- [Tokenization and the Noiseless Channel](https://mlsanity.com/paper/2306.16842/) (2023)
- [Language Modelling with Pixels](https://mlsanity.com/paper/2207.06991/) (2022)
- [Automata-based constraints for language model decoding](https://mlsanity.com/paper/2407.08103/) (2024)
- [Robust Open-Vocabulary Translation from Visual Text Representations](https://mlsanity.com/paper/2104.08211/) (2021)
- [Fishing for Magikarp: Automatically Detecting Under-trained Tokens in Large Language Models](https://mlsanity.com/paper/2405.05417/) (2024)
- [MYTE: Morphology-Driven Byte Encoding for Better and Fairer Multilingual Language Modeling](https://mlsanity.com/paper/2403.10691/) (2024)
- [CRANE: Reasoning with constrained LLM generation](https://mlsanity.com/paper/2502.09061/) (2025)
- [A Formal Perspective on Byte-Pair Encoding](https://mlsanity.com/paper/2306.16837/) (2023)

## Built on by (most cited first, 3 of 3)

- [The Roots of Performance Disparity in Multilingual Language Models: Intrinsic Modeling Difficulty or Design Choices?](https://mlsanity.com/paper/2601.07220/) (2026)
- [Cybersecurity is the True Frontier for Generative AI Success or Failure](https://mlsanity.com/paper/2606.28929/) (2026)
- [Faster Superword Tokenization](https://mlsanity.com/paper/2604.05192/) (2026)

## Abstract (arXiv)

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.