From Language Models over Tokens to Language Models over Characters

Motivation

• Token-level interfaces can change relative continuation probabilities when a shared character prefix moves across the prompt boundary, producing failures such as incorrect completions after trailing whitespace.The paper formalizes this prompt boundary problem and attributes it to conditioning on τ(σ) rather than token strings that best match the character prompt.Source: §1 · pp. 1–2

Related approach

• Token healing mitigates some boundary failures by backing up and constraining the next token, but backing up one token fails on Hello,␣worl, yielding Hello,␣worlwide instead of Hello,␣world.The paper motivates a more general covering-based solution because one-token backup is insufficient.Source: §1 · p. 2

Method

• A covering collects token strings whose decoded outputs have the character prompt as a prefix, allowing character-level probabilities to aggregate canonical and noncanonical tokenizations.The covering is defined through the decoding function, while probability-based pruning prioritizes likely token strings.Source: §1 · pp. 2–3
• The resulting character-level conditional probability sums covering members, so the model can select the likely next character even when tokenization boundaries do not align with the prompt.For the Hello,␣worl example, the method infers d as the most likely next character by taking the covering probability ratio for Hello,␣world and Hello,␣worl.Source: §1 · pp. 2–3

Applications

• The approach also supports character-substring surprisal and other character-level applications, including reading-time modeling with arbitrary substrings.Prior work found that flexible character-substring surprisals can predict reading time better than a fixed word-based notion.Source: §1 · p. 3

Empirical results

• Across four publicly available language models, limited computation produced accurate next-character conditional estimates at reasonably fast speeds and significantly improved compression rate in bits/byte.The experiments measure runtime, approximation accuracy, and compression when estimating corpus probability as characters rather than canonical tokens.Source: §1 · p. 3

Alphabets and prefix probability

• The formal setup represents alphabets as finite symbol sets and language models as distributions over finite strings, with prefix probabilities defined by the event that a sampled string begins with a given prefix.Single-symbol conditional prefix probabilities can be interpreted as distributions over the alphabet plus EOS.Source: §2.1 · p. 3, §2.2 · p. 4

Tokenized language models

• A tokenized language model samples a token string from p_Δ and decodes it with κ, inducing a distribution p_Σ over character strings.The induced probability accounts for every token string mapping to the same character string.Source: §2.3 · p. 4

Tokenization

• A character string can have multiple encodings, so evaluating only its deterministic canonical tokenization is incorrect when noncanonical encodings have nonzero model probability.For GPT2’s Hello, world example, probability is heavily concentrated on the canonical encoding, but the string has 78 possible encodings.Source: §2.3 · pp. 4–5

Character-level interface

• The character-level interface derives character probabilities from token-level probabilities by summing over token strings whose decoded outputs satisfy the relevant character constraints.The equations provide a complete character-level model when the required summations can be computed or approximated.Source: §2.3 · p. 5

Key properties of κ

• Strict-prefix monotone decoding ensures each token contributes at least one character and enables the algorithms to replace an infinite sum with a finite sum.Multiplicative, non-erasing decoders—including BPE and WordPiece—satisfy this property.Source: §2.4 · p. 5

3.1. Covering

• The covering converts prefix-probability computation into a finite sum over token strings whose decoded outputs extend the target character string.Strict-prefix monotonicity makes extensions remain valid, and the covering contains the relevant encodings.Source: §3.1 · pp. 5–6
• The complete covering can be large, but high-probability members are typically few enough to support practical enumeration and approximation.The paper notes that covering size may be impractical in general, while high-prefix-probability elements tend to be reasonably small.Source: §3.1 · p. 6, §3.2 · p. 6

3.2. Algorithms for pΣ(σ) and pΣ(σ)

• Without pruning, enumeration can be exponential in string length, with space O(|C(σ)|) and running time dominated by O(|∆| · |C(σ)|).These bounds apply under assumptions about constant-time decoding extensions and cached token-model evaluations.Source: §3.2 · pp. 6–7
• Beam pruning makes the approximation linear in character-string length, with larger K improving accuracy and exactness approached as K reaches the largest intermediate covering.The proposed pruning heuristic controls the speed–accuracy tradeoff through the beam parameter K.Source: §3.2 · p. 7

3.4. Conditional Generation p∆|Σ(δ | σ)

• The conditional generation algorithm is exact and generates samples from p∆|Σ(· | σ), while character-at-a-time generation is correct but slower.The faster method samples a minimally covering token string before completing the sequence in token space.Source: §3.4 · p. 8

Setup

• The study uses Llama-3.2-1B, Meta-Llama-3.1-8B, DeepSeek-R1-Distill-Llama-8B, and phi-4 (14B) on wikitext-103-v1.Experiments use GPU batching and a trie-based implementation for efficient evaluation.Source: §4 · p. 8

Results

• Across models, increasing K decreases speed and error, with error flattening after K ≥8 and larger models running more slowly because evaluation takes longer.The speed–error tradeoff is nonlinear, with sharper error increases at higher processing speeds.Source: §4 · p. 9
• Average per-byte surprisal is significantly lower than the canonically tokenized baseline under all models.The method accounts for probability assigned to noncanonical tokenizations and can identify likely noncanonical tokenizations missed by the baseline.Source: §4 · p. 9
• The paper concludes that the explored models concentrate probability mass on a few tokenizations, enabling accurate prefix-probability estimates with small K.This concentration explains why increasing K does not substantially reduce surprisal.Source: Conclusion · p. 9, §4 · p. 9

Impact

• The primary impact is a more predictable, user-friendly interface for working with tokenized language models.The paper connects this impact to mitigating unintended behaviors such as the prompt-boundary problem.Source: Impact Statement · p. 9

Scope

• The method is expected to work well with deterministic tokenizers, whereas stochastic tokenizers may require large beams and make the approach expensive.Sampling-based methods may offer a better speed–accuracy tradeoff for stochastic-tokenizer settings.Source: Limitations · p. 9

Supplementary Results

• The supplementary results provide Figure 1’s experimental data in tabular form.Source: A. Supplementary Results · p. 12

• The evaluation lists Llama-3.2-1B and Meta-Llama-3.1-8B as compared models.Source: §A.1 · p. 12
• The reported metrics are JSD / byte and bytes / sec.Source: §A.1 · p. 12
• The evaluation also lists DeepSeek-R1-Distill-Llama-8B and phi-4 (14B).Source: §A.1 · p. 12

• The comparison includes a Canonically Tokenized Baseline Model measured in bits / byte.Source: §A.2 · p. 13
• Llama-3.2-1B and Meta-Llama-3.1-8B are reported with bits / byte and bytes / sec.Source: §A.2 · p. 13
• DeepSeek-R1-Distill-Llama-8B and phi-4 (14B) are likewise reported with bits / byte and bytes / sec.Source: §A.2 · p. 13

Proof of Proposition 1

• The proof derives the character-level prefix probability by expanding cases and using each summand’s unique minimal prefix covering σ.The argument separately handles ε and uses prefix-monotonicity properties of the tokenizer.Source: B. Proof of Proposition 1 · p. 14

Covering-size bounds

• The covering-size bound is parameterized by tokenizer fertility F and munch M, with a recurrence-based inductive proof.The munch measures the largest number of characters introduced by adding one token; for BPE it is the longest detokenization, while GPT-2’s munch is 128.Source: C. The Size of the Covering · pp. 15–16
• C(N) takes Fibonacci-style forms in the general case, including F^N Fib(N, M), while special cases yield 2^N or F(1 + F)^N.The cited corollary distinguishes the cases M = N, F = 1; M = N, F ≥ 0; and the remaining case.Source: C. The Size of the Covering · p. 16

Exponential covering size

• A multiplicative tokenizer can produce exponentially many covering elements: |C(σ)| grows as Ω(2^|σ|) in the constructed example.The lower bound follows from counting nonnegative integer solutions to 1m + 2n = N.Source: C. The Size of the Covering · p. 16

Bundled beam summing

• Bundles group token sequences into compact objects while probability tries filter next tokens that disagree with the next character.This grouping improves the per-iteration filtering cost by reasoning about compatible extensions in bulk.Source: D. Bundled Beam Summing Implementation · p. 17

Bundle representation

• Each bundle stores prefix probability, token string, character string, and a local probability trie augmented with EOT.The trie supplies character-level probabilities for possible next tokens conditioned on the token string.Source: D. Bundled Beam Summing Implementation · pp. 17–18

Correctness correspondence

• unbundle_beam(beam(σ)) returns precisely the same elements as the unbundled enum_cover(σ) with bucket-based pruning parameter K, up to reordering.Source: D. Bundled Beam Summing Implementation · p. 18

• conditional_token_generation(σ) generates samples according to p∆|Σ(· | σ) for every σ ∈Σ∗.Source: E. Proof of Proposition 2 · p. 19
• The proof selects a prefix δ′ of an arbitrary sample δ that reaches the conditioning string, then writes δ as δ′·δ′′.Source: E. Proof of Proposition 2 · p. 19
• Correctness follows because the algorithm samples δ′ using the equation’s right factor and δ′′ using its left factor, yielding probability p∆|Σ(δ | σ).Source: E. Proof of Proposition 2 · p. 19

Token Healing Baseline

• The token-healing baseline has significantly higher surprisal and error than the paper’s methods and is not considered a competitive approximation.Source: F. Token Healing Baseline · p. 20
• The approximate covering Cheal(σ) is a subset of the full covering C(σ), with size bounded by the token alphabet: |Cheal(σ)| ≤ |∆|.Source: F. Token Healing Baseline · p. 20
• Construction tokenizes σ, builds a probability trie for all but the final token, and queries final-token character suffixes to compute next-character probabilities.Source: F. Token Healing Baseline · p. 20
• Compared with the beam algorithm, token_healing_cover performs extreme pruning by returning exactly one bundle and produces character-level rather than token-level predictions.Source: F. Token Healing Baseline · p. 20
• The approximation can still underweight d after conditioning on Hello,␣worl, for the same reasons associated with token healing in the paper’s motivating example.Source: F. Token Healing Baseline · p. 20

Probability-Based Pruning Heuristic

• Probability-based pruning uses threshold θ to avoid language-model evaluations for low-probability prefixes, reducing the bottleneck while extending the speed–accuracy experiments.Source: G. Probability-Based Pruning Heuristic · pp. 21–22, Figure 2 · p. 22