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

• URL: http://arxiv.org/abs/2511.05578v1
• Date: Wed, 05 Nov 2025 00:08:01 GMT
• Title: UTF-8 Plumbing: Byte-level Tokenizers Unavoidably Enable LLMs to Generate Ill-formed UTF-8
• Abstract summary: Subword tokenization segments input text according to a pre-defined vocabulary to feed it into a language model.<n>Using code points means that all members incrementally are valid-8 characters.<n>Beginning with bytes avoids out-of-vocabulary errors with only 256 initial members.
• Score: 11.900027560734145
• License: http://creativecommons.org/licenses/by-sa/4.0/
• 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.

Related papers

• Beyond Perplexity: UTF-8 Validity in Byte-aware Language Models [20.9586694123981]
  Byte-level tokenization enables language models to handle any Unicode input, but models can generate invalid-8 sequences when encountering rare or unseen characters.<n>We investigate the relationship between training scale and-8 generation reliability with a 355 parameter model trained on 80B tokens from a balanced multilingual corpus of English, Japanese, and Chinese.<n>In context-free generation, rare characters achieve higher structural validity than common characters, suggesting over-specialization of frequent character representations.
  arXiv  Detail & Related papers  (2026-06-12T05:03:55Z)
• Back to Bytes: Revisiting Tokenization Through UTF-8 [25.766926865651936]
  We present a minimalist byte-level tokenizer that maps text exactly to IDs corresponding to the underlying text's-8-8 encoding.<n>Our implementation never introduces out-of-range IDs.
  arXiv  Detail & Related papers  (2025-10-19T20:06:12Z)
• Broken Tokens? Your Language Model can Secretly Handle Non-Canonical Tokenizations [83.93566096400723]
  We find that instruction-tuned models retain up to 93.4% of their original performance when given a randomly sampled tokenization.<n>Character-level segmentation improves string manipulation and code understanding tasks by up to +14%.<n>Right-aligned digit grouping enhances large-number arithmetic by +33%.
  arXiv  Detail & Related papers  (2025-06-23T18:02:26Z)
• Sampling from Your Language Model One Byte at a Time [82.71473348639489]
  Tokenization can introduce distortion into the model's generations, known as the Prompt Boundary Problem (PBP)<n>We present an inference-time method to convert any autore LM with a BPE tokenizer into a character-level or byte-level LM.<n>Our method efficiently solves the PBP and is also able to unify the vocabularies of language models with different tokenizers.
  arXiv  Detail & Related papers  (2025-06-17T02:37:04Z)
• BPE Stays on SCRIPT: Structured Encoding for Robust Multilingual Pretokenization [0.0]
  SCRIPT (Script Category Representation in PreTokenization) is a novel encoding scheme that bypasses byte-8 conversion by using initial tokens based on Unicode script and category properties.<n>Our experiments demonstrate that SCRIPT-BPE achieves competitive compression while eliminating encoding-based penalties for non-Latin-script languages.
  arXiv  Detail & Related papers  (2025-05-30T15:12:41Z)
• From Language Models over Tokens to Language Models over Characters [54.123846188068384]
  Modern language models are internally -- and mathematically -- distributions over $ittoken$ strings rather than $itcharacter$ strings.<n>This paper presents algorithms for converting token-level language models to character-level ones.
  arXiv  Detail & Related papers  (2024-12-04T21:19:20Z)
• Tokenization as Finite-State Transduction [24.19959327497118]
  We introduce a finite-state framework which can efficiently encode all possible tokenizations of a regular language. We show that Byte-Pair. Match (BPE) and MaxPiece (WordPiece) fit within this framework. An application of this is to guided generation, where the outputs of a language model are constrained to match some pattern.
  arXiv  Detail & Related papers  (2024-10-21T07:10:07Z)
• Local Byte Fusion for Neural Machine Translation [19.16966721276286]
  Subword tokenization schemes are the dominant technique used in current NLP models. Byte-based methods i.e. tokenization into byte sequences are an alternative. Experiments on multilingual translation, zero-shot cross-lingual transfer, and domain adaptation reveal a consistent improvement over traditional models.
  arXiv  Detail & Related papers  (2022-05-23T17:49:02Z)
• Charformer: Fast Character Transformers via Gradient-based Subword Tokenization [50.16128796194463]
  We propose a new model inductive bias that learns a subword tokenization end-to-end as part of the model. We introduce a soft gradient-based subword tokenization module (GBST) that automatically learns latent subword representations from characters. We additionally introduce Charformer, a deep Transformer model that integrates GBST and operates on the byte level.
  arXiv  Detail & Related papers  (2021-06-23T22:24:14Z)
• Neural Machine Translation without Embeddings [44.129310924201604]
  Many NLP models operate over sequences of subword tokens produced by hand-crafted tokenization rules and subword induction algorithms. A simple universal alternative is to represent every computerized text as a sequence of bytes via-8. Experiments on byteto-byte machine translation from English to 10 different languages show a consistent improvement in BLEU, rivaling character-level and even standard subword-level models.
  arXiv  Detail & Related papers  (2020-08-21T09:54:11Z)
• 2kenize: Tying Subword Sequences for Chinese Script Conversion [54.33749520569979]
  We propose a model that can disambiguate between mappings and convert between the two scripts. Our proposed method outperforms previous Chinese Character conversion approaches by 6 points in accuracy.
  arXiv  Detail & Related papers  (2020-05-07T10:53:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.