Research map / Large language models / Language, safety and interpretability

From Language Models over Tokens to Language Models over Characters

ICML 2025 · Large language models › Language, safety and interpretability · approach: Controlled text generation · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Presents exact and beam-approximate algorithms that convert token-level language models (BPE) into character-level ones via a finite "covering" of character prefixes, fixing the prompt boundary problem and improving bits/byte.

Problem

Token-level language models are distributions over token strings, so character-level prompts and character-level probabilities (prefix and next-character probabilities) are ill-defined or distorted, causing the prompt boundary problem.

Approach

Define a covering of a character string: the minimal token strings whose decoding has the character string as a prefix. Character-level prefix probability is the sum of token-level probabilities over this finite covering, with a beam-search pruning heuristic giving approximate, linear-time computation and an exact conditional token generation procedure for prompts.

Key results

• Beam summing with K=8 achieves JSD/byte around 0.00003-0.00005 across four models relative to K=128 reference, with error flattening after K>=8.
• Character-level surprisal under beam summing (e.g., Llama-3.2-1B 0.635 bits/byte) is substantially lower than the canonical tokenization baseline (0.76 bits/byte).
• Speed decreases with beam size; e.g., Llama-3.2-1B runs at 115 bytes/sec at K=2 and 4.91 bytes/sec at K=128 on an L40S GPU.

Measured effects reported in the paper

Surprising findings

• The canonical tokenization baseline has notably higher bits/byte than character-level estimates, because noncanonical tokenizations carry substantial probability mass and the most likely tokenization is often noncanonical.
• Increasing beam size K does not significantly decrease surprisal, suggesting even greedy-ish beams cover the mass adequately.

Limitations

• Beam summing needs a very large beam size if the model does not concentrate mass on few tokenizations, e.g., models trained with stochastic tokenizers such as BPE-dropout or UnigramLM.
• Exact covering size can be exponential in string length.
• Experiments only cover four models and wikitext-103 test bytes.

Experimental setup

Datasets: wikitext-103-v1

Benchmarks: wikitext-103-v1

Metrics: Jensen-Shannon distance per byte surprisal (bits/byte) bytes/sec

Baselines: canonical tokenization surprisal token healing cover

Builds on: byte-pair encoding token healing vLLM

Closest papers by meaning

• Exact Byte-Level Probabilities from Tokenized Language Models for FIM-Tasks and Model Ensembles (ICLR 2025 · similarity 0.90)
• Broken Tokens? Your Language Model can Secretly Handle Non-Canonical Tokenizations (NeurIPS 2025 · similarity 0.89)
• The Foundations of Tokenization: Statistical and Computational Concerns (ICLR 2025 · similarity 0.89)
• An Analysis of Tokenization: Transformers under Markov Data (NeurIPS 2024 · similarity 0.89)
• Language Models over Canonical Byte-Pair Encodings (ICML 2025 · similarity 0.89)
• Over-Tokenized Transformer: Vocabulary is Generally Worth Scaling (ICML 2025 · similarity 0.88)