Understanding and Mitigating Tokenization Bias in Language Models

🎯 Pitch

Standard tokenizers like BPE introduce a systematic sampling bias that distorts next-character probabilities regardless of training scale or data volume. The authors show this bias is structural—not a training artifact—and propose two algorithms that simulate token-free behavior from existing tokenized models without any fine-tuning.

1. Executive Summary

This paper analyzes and mitigates a sampling bias induced by tokenization in autoregressive language models, showing that popular encoding schemes—maximum prefix encoding (MPE, used in WordPiece) and byte-pair encoding (BPE, used in Llama)—produce next-character probability estimates that deviate from the token-free ground truth even with infinite training data. The authors propose two novel algorithms to correct this bias—the Maximum Prefix Correction (MPC) algorithm for MPE and the Byte-Pair Correction (BPC) algorithm for BPE—neither of which requires finetuning the model and whose complexity scales linearly with sequence length for MPE. Empirically validated on a 3rd-order Markov chain using a GPT-2–style model, the methods accurately recover the true transition probabilities while the conventional baseline of directly prompting tokens exhibits significant distortion (e.g., outputting probability 1.0 for a character whose true probability is α under MPE), establishing that tokenized language models implicitly learn character-level information and that this information can be extracted without additional training, but only when the tokenization-induced invalid encoding structure is explicitly accounted for.

2. Context and Motivation

The Core Problem: Tokenization Introduces Unrecoverable Sampling Bias

The fundamental gap this paper addresses is deceptively simple: when a language model is trained on tokenized text with standard encoding algorithms like maximum prefix encoding (MPE) or byte-pair encoding (BPE), the model's predictions at the character level diverge from the true data distribution in ways that cannot be fixed by adding more training data or scaling up the model. This is not an approximation error or a training deficiency—it is a structural bias introduced by the tokenization procedure itself.

To understand why this matters, consider what happens when you prompt a tokenized LM. You type a string of characters—say, "A"—and ask the model to predict the next character. Behind the scenes, the string gets encoded into tokens using a vocabulary and an encoding algorithm (e.g., WordPiece for BERT, BPE for Llama). The model then outputs a probability distribution over possible next tokens. To convert this to a next-character prediction, the natural approach is to sum the probabilities of all tokens whose decoded form starts with the desired character. The paper demonstrates that this naïve marginalization is systematically wrong: the resulting character probabilities do not match what a token-free model trained on the same data would produce.

The paper crystallizes this as the next-character sampling bias (Definition 2.1). Formally, let $x_n^1$ be a prompt string with tokenization $t_i^1 = \text{encode}(x_n^1)$ . The ground-truth probability of the next character being some value is $P_{\text{gt}}(x_{n+1} \mid x_n^1)$ . But what the tokenized model gives you—after marginalizing over tokens—is $P_{\text{gt}}(x_{n+1} \mid t_i^1) = \sum_{t \in E} P_{\text{gt}}(t_{i+1}=t \mid t_i^1)$ , where $E$ is the set of tokens whose decoded form starts with $x_{n+1}$ . The bias exists precisely when these two quantities are unequal:

$P_{\text{gt}}(x_{n+1} \mid x_n^1) \neq P_{\text{gt}}(x_{n+1} \mid t_i^1)$

The paper's Markov chain example (Section 2.2, Figure 1) makes this concrete in a way that reveals why it is a fundamental problem rather than a minor approximation error. Consider a simple two-state Markov chain over characters $\{A, B\}$ , where $P(x_2 = B \mid x_1 = A) = \alpha$ and the vocabulary is $V = \{\text{"AA"}, \text{"A"}, \text{"B"}\}$ . When the prompt is the single character "A", the MPE encoding produces the token "A". But here's the crucial observation: under MPE rules, any string that starts with token "A" must have "B" as its next token—otherwise, MPE would have merged "A" with the following "A" to produce the longer token "AA" instead. Consequently, the tokenized model trained optimally on this data will always predict $P(t_2 = \text{"B"} \mid t_1 = \text{"A"}) = 1.0$ , regardless of the true value of $\alpha$ . The model literally cannot express the correct probability $\alpha$ because the tokenization structure has eliminated the possibility of the next character being "A" from the conditioning event $t_1 = \text{"A"}$ . Increasing the training set size does nothing to fix this—an optimally trained model on infinite data would still produce exactly the same biased estimate.

Why This Problem Is Both Practically Important and Theoretically Significant

The practical implications are immediate and widespread. Virtually every deployed autoregressive LM—GPTs, Llama, Gemini, BERT-based models—uses subword tokenization. When users interact with these models, they type character strings and receive character strings back. The model's internal representation operates on tokens, but the interface is characters. Any discrepancy between the token-conditioned and character-conditioned distributions means that what the user asks for (a character-level continuation) is not what the model actually computes, even setting aside all other sources of model error.

This bias manifests in several documented failure modes that the paper situates its work within (Section 1, Appendix A):

Sensitivity to spelling and morphology (Xue et al., 2022): Tokenization can make models brittle to character-level variations because the encoding boundary changes how the conditioning context is represented, altering the effective conditioning event.
Unfairness across languages (Petrov et al., 2024): Different languages tokenize differently under the same encoding algorithm—a character sequence that is one token in English might be two tokens in another language, changing the conditioning structure and potentially the model's predictions.
Poor arithmetic performance (Singh & Strouse, 2024): Arithmetic tasks are fundamentally character-level (digits), and tokenization can group digits in ways that obscure the digit-by-digit structure needed for correct computation.
Domain adaptation failures (Liu et al., 2023a): When a model encounters a new domain with different tokenization patterns (e.g., code, mathematical notation, chemical formulas), the mismatch between the tokenization structure and the character-level structure produces unreliable outputs.

These are not merely training artifacts that better data or larger models can fix—they are structural consequences of the encoding scheme that the paper formalizes through the concept of invalid encodings (Definition 2.2). An encoding is invalid if re-encoding its decoded form produces a different token sequence. For example, with vocabulary $V = \{\text{"c"}, \text{"a"}, \text{"t"}, \text{"at"}, \text{"cat"}\}$ , the encoding ["c", "at", "t"] is invalid because decoding gives "catt", and re-encoding "catt" under MPE gives ["cat", "t"]—not the original sequence. Proposition 2.3 formalizes the devastating consequence: an optimally trained tokenized LM assigns zero probability to all strings that would produce invalid encodings, meaning entire regions of the character-level probability space become inaccessible to the model simply because of how tokens are defined.

The theoretical significance goes deeper. The paper's framework reveals that tokenized LMs and token-free LMs are statistically equivalent objects viewed through different conditioning lenses. A tokenized LM trained on data from a token-free ground-truth distribution implicitly learns the character-level distribution—the information is there in the weights—but the model's standard interface (next-token prediction given token history) doesn't give you direct access to it. The bias is an interface problem, not a learning problem. This reframes the entire debate about whether tokenization is harmful: the model can represent character-level information, but extracting it requires understanding and correcting for the encoding structure.

Where Prior Approaches Fall Short

The paper identifies several lines of prior work that attempt to address tokenization-related issues, each with specific limitations that the present work overcomes.

Fine-tuning with new vocabularies (Chen et al., 2023; Liu et al., 2023b; Minixhofer et al., 2024) attempts to adapt a pretrained model to a different tokenization scheme by modifying the embedding layer and continuing training. While this can improve performance on target domains, it has three fundamental shortcomings that the paper highlights (Section 1):

It complicates the training process and requires domain-specific expertise in vocabulary design and training hyperparameter selection.
It doesn't provide theoretical understanding of whether the observed limitations actually arise from tokenization or from suboptimal model training. Performance improvements might come from the additional training itself rather than from fixing a tokenization problem.
Most critically, it doesn't address the structural bias problem. Even with a perfectly adapted vocabulary, the model still operates in the token domain, and the character-token mismatch persists—the new tokenization scheme has its own set of invalid encodings and its own sampling bias structure. Fine-tuning rearranges the bias but doesn't eliminate it.

Token-free language models (Yu et al., 2024; Nawrot et al., 2022; Tay et al., 2021) operate directly on characters or bytes, eliminating tokenization entirely. This is the most principled solution—no tokenization means no tokenization bias. However, as the paper notes (Section 1), these models face a severe practical limitation:

"it significantly increases the context length, resulting in performance that still lags behind the SOTA tokenized LMs"

A character-level model processing a 100-character string needs 100 processing steps, while a tokenized model might need only 20–30 tokens for the same string. Since transformer complexity scales quadratically with sequence length, this compression advantage is enormous. Token-free models must either accept this computational burden or develop new architectures (like the multi-scale transformers in MegaByte), but neither approach has yet matched the efficiency-performance Pareto frontier of tokenized models. The paper acknowledges that token-free modeling is a promising direction but positions its own work differently: rather than abandoning tokenization, show that tokenized models already contain token-free knowledge and develop methods to extract it.

Stochastic tokenization for evaluation (Cao & Rimell, 2021; Chirkova et al., 2023) proposes using stochastic tokenizers (like BPE-dropout; Provilkov et al., 2019) at test time to evaluate perplexity scores by marginalizing over multiple possible tokenizations. The paper identifies a subtle but important flaw (Appendix A): these evaluations are performed on models trained with deterministic tokenization. Proposition 2.3 shows that such models assign zero probability to many token sequences that stochastic tokenizers might produce, because those sequences correspond to invalid encodings under the training tokenizer. The model was never exposed to these token sequences during training, so its predictions on them are, at best, undefined and, at worst, arbitrary. The paper frames this as evaluating the model "under different encodings" being "suboptimal" (Remark 1 following Proposition 2.3)—the model's probability estimates are only meaningful for valid encodings under its training tokenizer.

Heuristic boundary-correction methods (Dagan et al., 2024; guidance ai, 2023) address a related but narrower problem: language models sometimes struggle to generate text near token boundaries because the prompt's last partial token creates an ambiguity about what the model should complete. These methods use heuristics to adjust the generation process—for example, by "prompting" the model with partial tokens or by backtracking when generation produces an undesired token boundary. The paper acknowledges this similarity (Appendix A) but distinguishes its contribution as theoretically grounded rather than heuristic:

"These methods, however, are heuristic and only applicable to certain scenarios. On the other hand, our bias removal algorithm is theoretically correct, versatile for various situations, and enables conversion between token-free and tokenized LMs due to its accurate representation of conditional sampling distributions."

Theoretical analyses of tokenization (Rajaraman et al., 2024; Zouhar et al., 2023) have examined tokenization through information-theoretic lenses, but the paper notes a conflict in the literature: some work finds compression beneficial (Gallé, 2019; Gutierrez-Vasques et al., 2023) while other work identifies counterexamples (Cognetta et al., 2024; Schmidt et al., 2024). The paper's approach is complementary: rather than asking whether tokenization is good or bad overall, it identifies a specific, provable bias that exists regardless of whether tokenization provides net benefits, and provides an algorithm to remove it.

How This Paper Positions Itself

The paper positions itself at the intersection of two research directions—theoretical understanding of tokenization and practical model evaluation/correction—and makes contributions to both.

On the theoretical side, the paper provides what previous work lacked: a formal characterization of why tokenization produces sampling bias, expressed through the concepts of invalid encodings (Definition 2.2) and token-induced zero probability (Proposition 2.3), and when the character and token domains align, expressed through the special subset of tokens $V^*$ (tokens that cannot be substrings of any other token) and the resulting equivalence of conditioning events (Proposition 3.1, Corollary 3.2). This theoretical apparatus is what enables the correction algorithms to work—it identifies the precise conditions under which the character-level and token-level distributions can be equated, and provides a factorization (Equation 1) for handling cases where they cannot.

On the practical side, the paper offers algorithms that are:

Training-free: No finetuning, no additional data, no modification to model weights. The algorithms operate purely at inference time by making structured queries to the existing tokenized LM.
Provably correct (for optimally trained models): The MPC and BPC algorithms exactly recover the character-level distribution that the tokenized model implicitly learned from tokenized training data.
Of manageable complexity: For MPE, the MPC algorithm's complexity—measured in number of model forward passes—scales linearly with the query string length. This is crucial because it means the correction does not impose an exponential or otherwise prohibitive computational burden.
General: The methods work for both MPE (through the MPC algorithm described in Section 3.2) and BPE (through the BPC algorithm described in Appendix H), covering the two most widely used encoding families.

The paper explicitly frames its contribution as demonstrating that tokenized and token-free models are statistically equivalent—the apparent gap between them is an artifact of incorrectly mapping between character and token conditioning events, not a fundamental limitation of what tokenized models can represent. This reframing has direct implications:

For evaluation: Character-level perplexity can be computed from tokenized LMs using the correction algorithms, providing a more principled evaluation metric that doesn't confound tokenization artifacts with model quality.
For model transfer: Since any tokenized model implicitly learns the token-free distribution, it is theoretically possible to simulate the behavior of a model trained with a different vocabulary without finetuning—by first extracting the token-free distribution and then projecting it onto the target tokenization scheme (though the paper notes this as a direction for future work rather than a completed result).
For the tokenization debate: The paper's results suggest that the question should not be "is tokenization harmful?" but rather "how do we correctly interface with tokenized models to access what they've actually learned?" The answer provided is: by explicitly accounting for the encoding structure through theoretically grounded correction algorithms.

3. Technical Approach

3.1 Reader Orientation

This paper builds a probabilistic correction layer that sits between a user's character-level query and a tokenized language model's token-level predictions, transforming the model's next-token probabilities into unbiased next-character probabilities without modifying the model itself. The system solves the problem that tokenized LMs structurally cannot express certain character-level probabilities correctly—even with infinite training data—by algorithmically marginalizing over the implicit character-level information that the model has nonetheless learned, using only the token-level interface that the model exposes.

3.2 Big-Picture Architecture (Diagram in Words)

The system has three major components working in sequence:

The Tokenized Language Model (fixed, black-box): A pretrained autoregressive LM that accepts a sequence of tokens $t_i^1$ and outputs a probability distribution over the next token $P(t_{i+1} \mid t_i^1)$ . The model is assumed to have been trained optimally on tokenized data under a specific encoding scheme (MPE or BPE) with a known vocabulary $V$ . The model's internal weights are never accessed or modified.
The Character-Token Refactoring Module: Given a character-level prompt $x_n^1$ and a target continuation string $x_{n+1}^N$ , this module determines how to factor the desired character-level conditional probability $P(x_{n+1}^N \mid x_n^1)$ into a ratio of token-conditioned probabilities that the LM can compute. It identifies a special token boundary (where the last token belongs to $V^*$ , the set of tokens not contained as substrings within any other token) that makes the character and token conditioning events equivalent.
The Correction Algorithm (MPC or BPC): This algorithm computes a single term of the form $P(x_{n_k+1}^N \mid t_k^1)$ —the probability of a character string continuation given a token history—by recursively decomposing the event into two complementary cases (the string is a prefix of the next token, or the next token is contained within the string) and summing their probabilities. For MPE, this is the Maximum Prefix Correction (MPC) algorithm (Algorithm 1, described in Section 3.2 of the paper). For BPE, this is the Byte-Pair Correction (BPC) algorithm (Algorithm 2, described in Appendix H).

Information flows as follows: a character-level prompt $x_n^1$ and target continuation $x_{n+1}^N$ enter the system → the refactoring module identifies the special token boundary $k$ where $t_k \in V^*$ and factors the query into a numerator term $P(x_{n_k+1}^N \mid t_k^1)$ and denominator term $P(x_{n_k+1}^n \mid t_k^1)$ → the correction algorithm computes each term by making structured queries to the frozen LM (one model forward pass per recursive step, each returning a full next-token distribution) and aggregating the results → the final character-level probability is returned as the ratio.

3.3 Roadmap for the Deep Dive

First, the computational foundation: the character-token refactoring step (Equation 1), which converts the character-conditioned query into token-conditioned terms the LM can handle, and the theoretical guarantee (Proposition 3.1, Corollary 3.2) that makes this conversion exact at special token boundaries.
Second, the Maximum Prefix Correction algorithm (Algorithm 1) in full operational detail: the Branch step, the Pass step, the Base Case, and the recursion structure—since this is the core computational engine and the reader needs to understand what happens at each model call.
Third, the subtle but critical assumption about model behavior: the invalid encoding structure (Proposition 2.3) and the Truncate-Renormalization procedure (Proposition G.1) that guarantees any LM can be post-processed to satisfy this assumption without degrading token-level perplexity—since the correction algorithm's correctness depends on it.
Fourth, the special vocabulary subset $V^*$ and its role in bridging character and token domains—since the entire refactoring approach hinges on identifying tokens that cannot be absorbed into larger tokens.
Fifth, the Byte-Pair Correction algorithm (Appendix H.2, Algorithm 2) for BPE, contrasting its cover-encoding enumeration strategy with MPC's recursive decomposition, since BPE is the dominant encoding scheme in modern LMs.

3.4 Detailed, Sentence-Based Technical Breakdown

This is primarily a theoretical correction paper whose core idea is that tokenized LMs implicitly learn character-level distributions, and these distributions can be extracted exactly by explicitly accounting for the encoding algorithm's structure when mapping between character-conditioned and token-conditioned probability queries.

3.4.1 The Refactoring Step: Converting Character Queries to Token Queries

The fundamental challenge is that the tokenized LM accepts and produces token sequences, but we want to compute character-level probabilities. The refactoring step bridges this gap by identifying conditions under which character and token conditioning events are equivalent, and factoring the query to exploit those conditions.

The core refactoring equation. Given a prompt string $x_n^1$ and a target continuation $x_{n+1}^N$ , the goal is to compute $P(x_{n+1}^N \mid x_n^1)$ —the probability that the next $N-n$ characters are $x_{n+1}^N$ , given that the previous $n$ characters were $x_n^1$ . Let $t_i^1 = \text{encode}(x_n^1)$ be the tokenization of the prompt. The refactoring equation is:

$P(x_{n+1}^N \mid x_n^1) = \frac{P(x_{n_k+1}^N \mid t_k^1)}{P(x_{n_k+1}^n \mid t_k^1)}$

where $k$ is the index of the last token in $\text{encode}(x_n^1)$ that belongs to $V^*$ (the set of tokens that are not a substring of any other token in the vocabulary), and $x_{n_k}^1 = \text{decode}(t_k^1)$ is the prefix of $x_n^1$ that corresponds to those first $k$ tokens. Importantly, $n_k \leq n$ , meaning the token boundary $k$ may cover fewer characters than the full prompt—the remaining characters $x_{n_k+1}^n$ are the "leftover" suffix handled by the correction algorithm.

What it computes: The desired character-level probability $P(x_{n+1}^N \mid x_n^1)$ is expressed as a ratio of two token-conditioned probabilities. The numerator $P(x_{n_k+1}^N \mid t_k^1)$ is the probability of the full continuation (from position $n_k+1$ to $N$ ) given the first $k$ tokens. The denominator $P(x_{n_k+1}^n \mid t_k^1)$ is the probability of just the prompt suffix (from $n_k+1$ to $n$ ) given those same tokens. Both terms have the same conditioning event $t_k^1$ (token history) and ask for character-level continuations—exactly the form that the correction algorithm (MPC or BPC) can compute.

Why this form: The factorization exploits a chain-rule identity: $P(x_{n+1}^N \mid x_n^1) = P(x_{n+1}^N \mid x_{n_k}^1, x_{n_k+1}^n) = P(x_{n_k+1}^N \mid x_{n_k}^1) / P(x_{n_k+1}^n \mid x_{n_k}^1)$ . The refactoring then replaces the character conditioning $x_{n_k}^1$ with the token conditioning $t_k^1$ in both numerator and denominator, which is valid precisely because $t_k \in V^*$ guarantees (via Corollary 3.2) that $P(\cdot \mid x_{n_k}^1) = P(\cdot \mid t_k^1)$ . Without this replacement, we would need a character-conditioned model—exactly what we lack. With it, both terms become computable by the correction algorithm using only the tokenized LM. If $t_k \notin V^*$ (i.e., no token in the encoding of the prompt belongs to $V^*$ ), the factorization would need a different $k$ —the paper notes that one can always find such a $k$ by scanning the encoding from right to left until finding a token in $V^*$ , and in practice, most LMs begin every sequence with a special start token (e.g., <start> in SentencePiece) that belongs to $V^*$ , making this always possible.

The boundary case. When the last token $t_i$ of $\text{encode}(x_n^1)$ is itself in $V^*$ , then $n_k = n$ (the special token boundary coincides with the end of the prompt), and the denominator $P(x_{n_k+1}^n \mid t_k^1)$ becomes $P(\text{empty} \mid t_k^1) = 1.0$ . The refactoring simplifies to $P(x_{n+1}^N \mid x_n^1) = P(x_{n+1}^N \mid t_i^1)$ , which can be computed directly by a single call to the correction algorithm. This is the common case when the prompt ends cleanly at a token boundary that cannot be subsumed.

The general case. When $t_i \notin V^*$ , the prompt ends mid-token from the perspective of $V^*$ . The leftover characters $x_{n_k+1}^n$ represent the suffix of the prompt beyond the last $V^*$ token. Both numerator and denominator must account for this suffix: the numerator computes the probability of the suffix plus the target continuation, while the denominator computes the probability of just the suffix. Their ratio isolates the conditional probability of the target continuation given that the suffix occurred—exactly what the chain rule prescribes.

3.4.2 The Theoretical Guarantee: Equivalence of Character and Token Conditioning at $V^*$ Boundaries

The refactoring step's validity rests on Proposition 3.1 and Corollary 3.2, which establish when the character-level and token-level conditioning events describe exactly the same set of possible strings.

Definition of $V^*$ : The special subset $V^* \subset V$ consists of all tokens $t^* \in V^*$ such that $t^*$ is not a substring of any other token in $V$ except itself. Operationally, if you take any token $t^* \in V^*$ and any other token $t \in V$ where $t \neq t^*$ , the string $t^*$ does not appear as a contiguous subsequence within $\text{decode}(t)$ . For example, if $V = \{\text{"AAA"}, \text{"AA"}, \text{"CB"}, \text{"A"}, \text{"B"}, \text{"C"}\}$ , then $V^* = \{\text{"AAA"}, \text{"CB"}\}$ because "AAA" contains "AA" and "A" as substrings, so "AA" and "A" cannot be in $V^*$ , while "CB" is not a substring of any other token. "B" contains no other tokens but "B" itself is a substring of "CB", so "B" \notin V^*$.

Proposition 3.1 interpretation: Let $s^* = x_n^1$ be the prompt string, with tokenization $t_i^1 = \text{encode}(s^*)$ . The proposition makes two claims:

$S(t_i^1) \subset S(x_n^1)$ : Any string $s$ whose first $i$ tokens are $t_i^1$ must have $x_n^1$ as a prefix. In probability terms, $P(x_n^1 \mid t_i^1) = 1.0$ . This is because the tokens $t_i^1$ decode to exactly $x_n^1$ , and any string that begins with those tokens must begin with those characters.
When $t_i \in V^*$ , we have $S(t_i^1) = S(x_n^1)$ : Not only does token conditioning imply character prefix (as above), but now character prefix also implies token conditioning. Any string $s$ that has $x_n^1$ as a prefix must have its first $i$ tokens be exactly $t_i^1$ . In probability terms, $P(t_i^1 \mid x_n^1) = 1.0$ . This bidirectional implication— $x_n^1$ occurs if and only if $t_i^1$ occurs—is what makes the two conditioning events equivalent.

Why $t_i \in V^*$ enables the reverse direction: The key insight is about boundary stability. When the last token $t_i$ is in $V^*$ , it cannot be a substring of any other token. This means that no matter what characters come after $x_n^1$ in the full string, they cannot merge with $t_i$ to form a longer token—because $t_i$ cannot appear as a substring within anything else. Consequently, the token boundary after $t_i$ is immutable: any string starting with $x_n^1$ will always have its first $i$ tokens determined exactly by the encoding of $x_n^1$ . If $t_i \notin V^*$ (e.g., "A" when "AA" exists in the vocabulary), appending characters could cause MPE to merge "A" with a following "A" into "AA", changing the tokenization and breaking the $S(x_n^1) \subset S(t_i^1)$ inclusion.

Corollary 3.2 interpretation: Given $t_i \in V^*$ , we have the direct substitution rules:

$P(x_{n+1}^N \mid x_n^1) = P(x_{n+1}^N \mid t_i^1)$

and similarly for future tokens:

$P(t_{i+1}^j \mid x_n^1) = P(t_{i+1}^j \mid t_i^1)$

The proof (Appendix D) uses the conditional probability chain:

$P(x_{n+1}^N \mid t_i^1) = P(x_{n+1}^N \mid t_i^1, x_n^1)$ because $P(x_n^1 \mid t_i^1) = 1.0$ (knowing the tokens implies knowing the characters).
Expand using Bayes: $= P(x_{n+1}^N, t_i^1 \mid x_n^1) / P(t_i^1 \mid x_n^1)$ .
$= P(x_{n+1}^N \mid x_n^1) \cdot P(t_i^1 \mid x_n^1, x_{n+1}^N) / P(t_i^1 \mid x_n^1)$ .
When $t_i \in V^*$ , we have $P(t_i^1 \mid x_n^1) = 1.0$ and $P(t_i^1 \mid x_n^1, x_{n+1}^N) = 1.0$ (the tokenization of the prefix is immutable regardless of what follows), so the ratio equals 1 and the original equality holds.

Practical consequence: The refactoring step always works because we can find some $k$ such that $t_k \in V^*$ . For the worst case where no token in the prompt's encoding belongs to $V^*$ (the prompt is entirely composed of tokens that can be subsumed), the paper's approach (Appendix E.1) is to look for the rightmost token that satisfies the condition. Since most LMs prepend a special start token (like <start>) that is in $V^*$ and is the first token of every encoding, $k=1$ always works, though using a larger $k$ reduces the computational burden on the correction algorithm by making the query string shorter.

3.4.3 The Maximum Prefix Correction (MPC) Algorithm: Core Mechanism

Algorithm 1 (Section 3.2 of the paper) computes $P(x_{n_k+1}^N \mid t_k^1)$ —the probability of observing a specific character string $x_{n_k+1}^N$ as the continuation, conditioned on the token history $t_k^1$ . Critically, this algorithm does not require $t_k \in V^*$ ; it works for any valid token history. The $V^*$ condition is only needed for the refactoring step that precedes it.

The central decomposition. The algorithm decomposes the event "the continuation is exactly $x_{n_k+1}^N$ " into two mutually exclusive and collectively exhaustive cases based on the relationship between the continuation string and the next token $t_{k+1}$ :

Branch case: The continuation string $x_{n_k+1}^N$ is a prefix of the next token $t_{k+1}$ . That is, there exists some token in the vocabulary whose decoded form starts with $x_{n_k+1}^N$ . In this case, the event "the next characters are $x_{n_k+1}^N$ " is realized exactly when the next token is one of those prefix-matching tokens.
Pass case: The continuation string $x_{n_k+1}^N$ is not a prefix of the next token. Under maximum prefix encoding rules, this means the next token must be entirely contained within $x_{n_k+1}^N$ as a prefix of the continuation—specifically, it must be the first token of $\text{encode}(x_{n_k+1}^N)$ . The remaining characters after this token form a shorter continuation query that can be handled recursively.

Formal probability decomposition. The marginalization underlying the algorithm is:

$P(x_{n_k+1}^N \mid t_k^1) = \sum_{t \in V} P(x_{n_k+1}^N, t_{k+1}=t \mid t_k^1)$

The vocabulary $V$ is partitioned into two disjoint sets:

$T_{\text{bval}} = \{t \in V \mid x_{n_k+1}^N \in \text{prefix}(\text{decode}(t))\}$ : tokens whose decoded form has $x_{n_k+1}^N$ as a prefix.
$T_{\text{pval}} = V \setminus T_{\text{bval}}$ : all remaining tokens.

The sum splits accordingly into bval (branch value) and pval (pass value):

$P(x_{n_k+1}^N \mid t_k^1) = \underbrace{\sum_{t \in T_{\text{bval}}} P(x_{n_k+1}^N, t_{k+1}=t \mid t_k^1)}_{\text{bval}} + \underbrace{\sum_{t \in T_{\text{pval}}} P(x_{n_k+1}^N, t_{k+1}=t \mid t_k^1)}_{\text{pval}}$

The Branch step (lines 3–4 of Algorithm 1). For each token $t \in T_{\text{bval}}$ , the joint probability simplifies because conditioning on $t_{k+1}=t$ makes the character event certain:

$P(x_{n_k+1}^N, t_{k+1}=t \mid t_k^1) = P(t_{k+1}=t \mid t_k^1) \cdot P(x_{n_k+1}^N \mid t_k^1, t_{k+1}=t) = P(t_{k+1}=t \mid t_k^1)$

where $P(x_{n_k+1}^N \mid t_k^1, t_{k+1}=t) = 1.0$ because $x_{n_k+1}^N$ is a prefix of $\text{decode}(t)$ by construction (if the next token is $t$ , its decoded form necessarily starts with $x_{n_k+1}^N$ ). Therefore:

$\text{bval} = \sum_{t \in T_{\text{bval}}} P(t_{k+1}=t \mid t_k^1)$

What it computes operationally: The algorithm collects all tokens in the vocabulary whose decoded form starts with the target string $x_{n_k+1}^N$ , queries the LM once for the full next-token distribution $P(t_{k+1} \mid t_k^1)$ , and sums the probabilities of those matching tokens. This is a single LM forward pass.

The Pass step (lines 10–13 of Algorithm 1). For tokens $t \in T_{\text{pval}}$ , the joint probability is zero for all except one specific token: the first token of the encoding of the continuation string. This follows from Proposition B.1 (Appendix B), which characterizes how MPE tokenization works within a string. Specifically, given that $x_{n_k+1}^N$ is not a prefix of the next token, the next token must be exactly $\text{encode}(x_{n_k+1}^N)_1$ —the first token that MPE would produce when encoding the continuation string. Any other token $t \in T_{\text{pval}}$ would produce an invalid encoding when followed by the remaining characters, which Proposition 2.3 guarantees has zero probability under an optimally trained LM.

Let $t^* = \text{encode}(x_{n_k+1}^N)_1$ be this specific token, and let $x_{n_k+1}^{n_k+l}$ be its decoded form (where $l = |\text{decode}(t^*)|$ is the number of characters it covers). Then:

$P(x_{n_k+1}^N, t_{k+1}=t^* \mid t_k^1) = P(t_{k+1}=t^* \mid t_k^1) \cdot P(x_{n_k+l+1}^N \mid t_k^1, t_{k+1}=t^*)$

The first factor is the LM's probability for token $t^*$ . The second factor is a recursive call to the same algorithm, but now with the updated token history $t_{k+1}^1$ (appending $t^*$ ) and a shorter continuation string $x_{n_k+l+1}^N$ (stripping off the characters covered by $t^*$ ). Thus:

$\text{pval} = P(t_{k+1}=t^* \mid t_k^1) \times \text{COMPUTE}(x_{n_k+l+1}^N, t_{k+1}^1)$

where $\text{COMPUTE}$ is the recursive invocation of the MPC algorithm (Algorithm 1).

What it computes operationally: The algorithm identifies the first token $t^*$ that MPE would produce for the continuation string, queries the LM once for $P(t_{k+1}=t^* \mid t_k^1)$ , and then makes a recursive call on the remaining characters. Each recursive call costs exactly one LM forward pass.

The Base Case (lines 6–8 of Algorithm 1). The recursion terminates when the remaining continuation string $x_j^N$ itself forms a complete token in the vocabulary—i.e., $\text{encode}(x_j^N) \in V$ . At this point, the event "the next characters are $x_j^N$ " can only be realized through the Branch case (the string is a prefix of the next token, and since it is a complete token, the next token is exactly that token or a token starting with it). The Pass case would require the next token to be a proper prefix of $x_j^N$ , but since $x_j^N$ is already a single token, its only prefixes are shorter strings, and the remaining characters after such a token would not form the target continuation. The algorithm therefore returns only bval (the sum over all tokens with $x_j^N$ as prefix) at the base case.

Complete recursive structure (Figure 2 visualization). Suppose the vocabulary is $V = \{\text{b}, \text{e}, \text{p}, \text{r}, \text{n}, \text{ep}, \text{een}, \text{beer}\}$ , the token history is $t_k^1$ , and the query string is "bee". The algorithm proceeds as:

Call 1 on "bee":
- Branch: $T_{\text{bval}} = \{\text{"beer"}\}$ , so $\text{bval}_1 = P(t_{k+1}=\text{"beer"} \mid t_k^1)$ .
- Pass: The first token of $\text{encode("bee")}$ is "b". So $\text{pval}_1 = P(t_{k+1}=\text{"b"} \mid t_k^1) \times \text{COMPUTE}(\text{"ee"}, [t_k^1, \text{"b"}])$ .
Call 2 on "ee" (with history $[t_k^1, \text{"b"}]$ ):
- Branch: $T_{\text{bval}} = \{\text{"een"}\}$ , so $\text{bval}_2 = P(t_{k+2}=\text{"een"} \mid t_k^1, t_{k+1}=\text{"b"})$ .
- Pass: The first token of $\text{encode("ee")}$ is "e" (since "ep" starts with "e" but MPE would need to see the next character to decide between "e" and "ep"—actually, under MPE with this vocabulary, $\text{encode("ee")} = [\text{"e"}, \text{"e"}]$ because "een" is not a prefix of "ee" and "ep" starts with "e" followed by "p", not "e"). So $\text{pval}_2 = P(t_{k+2}=\text{"e"} \mid t_k^1, \text{"b"}) \times \text{COMPUTE}(\text{"e"}, [t_k^1, \text{"b"}, \text{"e"}])$ .
Call 3 on "e" (base case): Since "e" is itself in the vocabulary, the algorithm returns $\text{bval}_3 = P(t_{k+3}=\text{"e"} \mid \dots) + P(t_{k+3}=\text{"ep"} \mid \dots) + P(t_{k+3}=\text{"een"} \mid \dots)$ (all tokens starting with "e").

The final result is the sum of all branch values at each level, weighted by the probability of reaching that level via the pass steps: $\text{Result} = \text{bval}_1 + P(\text{"b"}) \cdot \text{bval}_2 + P(\text{"b"}) \cdot P(\text{"e"}) \cdot \text{bval}_3$ .

Why this decomposition exhausts all possibilities: Every valid string that begins with $x_{n_k+1}^N$ after the token history $t_k^1$ must have the property that either the next token covers $x_{n_k+1}^N$ as a prefix (Branch case) or the next token is contained within $x_{n_k+1}^N$ (Pass case). There is no third option because MPE always produces the longest possible token at each step—if $x_{n_k+1}^N$ were neither a prefix of the next token nor containing the next token as its prefix, the encoding would be invalid, which has probability zero (Proposition 2.3). The recursion terminates because each Pass step consumes at least one character (the decoded form of $t^*$ ), so the remaining string strictly shortens, guaranteeing termination in at most $N - n_k$ recursive calls.

Complexity analysis. Each recursive call makes exactly one query to the LM to obtain the full next-token distribution $P(t_{k+1} \mid t_k^1)$ . The maximum recursion depth equals the length of the query string $N - n_k$ (in the worst case where each Pass step consumes exactly one character, which occurs when every character is its own token). Therefore, the number of LM forward passes scales as $O(N - n_k)$ , i.e., linearly with the number of characters in the query string. The cost of enumerating $T_{\text{bval}}$ (finding all tokens that start with a given string) is negligible compared to a transformer forward pass, as it involves simple string matching against the vocabulary.

3.4.4 The Invalid Encoding Structure and Why It Matters for Correctness

The MPC algorithm's Pass step relies on a critical property: when $x_{n_k+1}^N$ is not a prefix of the next token, exactly one token in $T_{\text{pval}}$ can have non-zero probability—namely, $\text{encode}(x_{n_k+1}^N)_1$ . For any other token $t \in T_{\text{pval}}$ , the encoding $[t_k^1, t]$ followed by the characters necessary to complete $x_{n_k+1}^N$ would be invalid, and the LM should assign zero probability to such events. This section explains why this is true, what assumptions it requires, and how to ensure the LM satisfies those assumptions.

Definition 2.2 (Invalid Encodings): A token sequence $t_i^1$ is invalid if $\text{encode}(\text{decode}(t_i^1)) \neq t_i^1$ . That is, if you decode the tokens back to a string and then re-encode that string using the same vocabulary and encoding algorithm, you get a different token sequence. Invalid encodings represent token sequences that the encoding algorithm would never produce from any input string.

Proposition 2.3 (Token-Induced Zero Probability): This proposition establishes three facts about an optimally trained tokenized LM:

$P_{\text{gt}}(t_i^1) = 0.0$ for any invalid encoding $t_i^1$ : Since the training data consists exclusively of valid encodings (every string in the dataset is encoded using the same algorithm), the model never sees an invalid token sequence during training, and its maximum-likelihood estimate assigns zero probability to it.
$P_{\text{gt}}(t_{i+1} \mid t_i^1)$ is undefined for invalid $t_i^1$ : The conditional probability $P(A \mid B) = P(A, B) / P(B)$ involves division by $P(B)$ , which is zero when $B$ is an invalid encoding. Formally, the conditional probability is undefined. Practically, a neural LM with softmax outputs will still produce some distribution, but these outputs are arbitrary artifacts of the softmax rather than meaningful probability estimates—the model was never trained to predict from invalid contexts.
$P_{\text{gt}}(t_{i+1} \mid t_i^1) = 0.0$ when $t_i^1$ is valid but $t_{i+1}^1$ is invalid: Even if the prefix is valid, appending a token that creates an invalid sequence has zero probability because such sequences never appear in the training data.
$P_{\text{gt}}(x_{n+1}^N \mid t_i^1) = 0.0$ when appending $x_{n+1}^N$ would change the tokenization of the prefix: More generally, for any character continuation that would cause the prefix tokens to be tokenized differently under MPE, the probability is zero. This follows because the original tokens $t_i^1$ would not be the encoding of the full string, meaning the event $(t_i^1, x_{n+1}^N)$ corresponds to a set of strings with measure zero under the data distribution.

Why this property is essential for the Pass step: In the MPC algorithm's Pass step, we claim that among all tokens in $T_{\text{pval}}$ (tokens that do NOT have $x_{n_k+1}^N$ as a prefix), only $\text{encode}(x_{n_k+1}^N)_1$ can have non-zero joint probability with the character event. The justification, formalized in Proposition B.1 (Appendix B), is that under MPE rules, the token boundaries within any valid encoding are deterministically constrained by the string content. Specifically, Proposition B.1 (Result 1) shows that for any string $s$ containing $x_n^1$ as a prefix, the first several tokens of $\text{encode}(s)$ must exactly match the tokens of $\text{encode}(x_n^1)$ up to the point where a token spans the boundary between $x_n^1$ and the subsequent characters. If the next token after the shared prefix is not $\text{encode}(x_{n_k+1}^N)_1$ , then the encoding would violate the MPE merge rules (specifically, a longer token would have been available at that position), making the encoding invalid and thus of zero probability by Proposition 2.3.

The practical problem: neural LMs with softmax outputs. Real neural LMs with softmax activation functions do not exactly satisfy Proposition 2.3. Because the softmax is strictly positive for all finite logits, the model will assign some tiny but non-zero probability to invalid continuations. This would cause the Pass step to need to sum over ALL tokens in $T_{\text{pval}}$ , not just $\text{encode}(x_{n_k+1}^N)_1$ , since each would have some small joint probability with the character event. This would explode the computational complexity.

The Truncate-Renormalization (TR) fix (Proposition G.1, Appendix G): The paper provides a principled post-processing step that converts any neural LM into one that exactly satisfies Proposition 2.3, while guaranteeing that the modified LM has lower (better) token-level perplexity than the original. The procedure is:

Identify the forbidden set: For any token history $t_i^1$ , define $\Phi^* = \{t \in V \mid t_{i+1}^1 \text{ is invalid}\}$ —the set of next tokens that would create an invalid encoding.
Zero out those probabilities: Set $\hat{P}(t_{i+1}=t \mid t_i^1) = 0$ for all $t \in \Phi^*$ .
Renormalize: For all remaining tokens $t \notin \Phi^*$ , set $\hat{P}(t_{i+1}=t \mid t_i^1) = P(t_{i+1}=t \mid t_i^1) / Z$ where $Z = \sum_{t' \notin \Phi^*} P(t_{i+1}=t' \mid t_i^1)$ is the sum of probabilities over valid continuations.

Why this works (Proposition G.1 proof sketch): Let $p$ be the true ground-truth distribution (which, by Proposition 2.3, has $p_i = 0$ for all invalid continuations). Let $q$ be the neural LM's distribution (with $q_i > 0$ for all $i$ due to softmax). Let $q^*$ be the TR-modified distribution. The KL divergence from $p$ to $q^*$ is:

$D_{\text{KL}}(p \parallel q^*) = \sum_i p_i \log\frac{p_i}{q^*_i} = \sum_{i \notin \Phi^*} p_i \log\frac{p_i}{q_i/Z} = \left[\sum_{i \notin \Phi^*} p_i \log\frac{p_i}{q_i}\right] + \log Z$

Since $Z \leq 1$ (the normalizing constant is the sum over a subset of the original probabilities), we have $\log Z \leq 0$ . Therefore:

$D_{\text{KL}}(p \parallel q^*) \leq \sum_{i \notin \Phi^*} p_i \log\frac{p_i}{q_i} = D_{\text{KL}}(p \parallel q)$

The TR-modified distribution is strictly closer to the ground truth in KL divergence. Since perplexity is the exponential of cross-entropy, and cross-entropy equals $H(p) + D_{\text{KL}}(p \parallel \cdot)$ , the TR model achieves lower (better) perplexity. This means the TR procedure is not just a hack to make the MPC algorithm efficient—it is a provably beneficial transformation that improves the model's quality on the token domain.

Practical implementation: The paper notes (Appendix G) that one can precompute the invalid token sets for all possible token histories, or compute them on-the-fly by checking Definition 2.2 (encode the decoded history plus candidate token and compare). For the MPC algorithm, the only history-dependent invalidity check needed in the Pass step is whether $t_{k+1} = t^*$ (the first token of the continuation's encoding) creates a valid or invalid encoding when appended to $t_k^1$ . The TR procedure ensures that all OTHER tokens in $T_{\text{pval}}$ have exactly zero probability, restricting the Pass sum to the single term $P(t_{k+1}=t^* \mid t_k^1)$ used in the algorithm.

3.4.5 The Special Vocabulary Subset $V^*$ and Its Role

The concept of $V^*$ —tokens that cannot appear as substrings of any other token in the vocabulary—is the linchpin connecting the character and token domains. Understanding why it works and how to find $V^*$ tokens in any vocabulary is essential for applying the refactoring step.

Formal definition: $V^* = \{t^* \in V \mid \forall t \in V, t \neq t^* \implies t^* \text{ is not a substring of } \text{decode}(t)\}$ . A token $t^*$ belongs to $V^*$ if no other token in the vocabulary, when decoded, contains the character sequence of $t^*$ as a contiguous subsequence.

Why $V^*$ tokens are "stable" under MPE: Consider what happens when you append characters after a string $x_n^1$ whose encoding ends with a token $t_i \in V^*$ . Under MPE, the algorithm scans left-to-right, always taking the longest possible token at each position. Could the newly appended characters cause a different tokenization of $x_n^1$ ? Only if some token boundary within $x_n^1$ shifts. For the last token $t_i$ to change, the appended characters would need to merge with $t_i$ to form a longer token. But $t_i \in V^*$ means $t_i$ cannot be a substring of any longer token—there IS no longer token containing $t_i$ . Therefore, the token boundary after $t_i$ is immutable: regardless of what follows, $t_i$ will remain as its own token, and consequently all earlier token boundaries (which were determined by MPE scanning from the left) also remain fixed. The encoding of $x_n^1$ is thus a deterministic function of $x_n^1$ alone, independent of context.

Finding $V^*$ in practice: For any given vocabulary, $V^*$ can be computed by substring checking: for each token $t$ , check whether $\text{decode}(t)$ appears as a substring of $\text{decode}(t')$ for any $t' \neq t$ . In typical BPE/WordPiece vocabularies, many tokens are NOT in $V^*$ . For instance, single-character tokens like "a" appear as substrings of nearly every longer token containing the letter "a", so they are not in $V^*$ . Tokens like "ing" might or might not be in $V^*$ depending on whether longer tokens like "bringing" or "singing" exist. The paper notes (Section 3.1, footnote) that most LMs include a special start token (e.g., <start> or <s>) that is not a substring of any regular vocabulary token, so $k=1$ (the first token) is always a valid choice for the refactoring step. However, using a larger $k$ (closer to the end of the prompt) reduces the length of the query string passed to the correction algorithm, improving computational efficiency.

Why the refactoring $k$ can exist even without a start token: Even if no token in the prompt's encoding belongs to $V^*$ (e.g., every token in the encoding appears as a substring of some other token), Proposition 3.1 and Corollary 3.2 still apply for ANY index $k$ where $t_k \in V^*$ , regardless of whether $k$ corresponds to the end of the prompt. The factorization in Equation 1 simply partitions the prompt into a prefix $x_{n_k}^1$ (whose encoding ends with a $V^*$ token) and a suffix $x_{n_k+1}^n$ . The suffix is handled by the correction algorithm as part of the query string. This means the algorithm always works by setting $k$ to be the rightmost token in the encoding that belongs to $V^*$ , or to $1$ if a start token exists.

The Markov chain example revisited through the $V^*$ lens: In Figure 1, the vocabulary is $V = \{\text{"AA"}, \text{"A"}, \text{"B"}\}$ . Which tokens are in $V^*$ ? "AA" is in $V^*$ because neither "A" nor "B" contains "AA" as a substring. "B" is in $V^*$ because "AA" and "A" do not contain "B" as a substring. "A" is NOT in $V^*$ because "AA" contains "A" as a substring. Now consider the prompt "A". Its encoding is ["A"], and "A" \notin V^*$. The refactoring would need to find the nearest $V^*$ token—which, in a full sequence, would be the start token or whatever token preceded this "A". If the prompt is just the single character "A" with no start token, the refactoring would set $k$ to the token before it (which might not exist), illustrating why start tokens are practically important. The bias phenomenon—the model outputting $P(t_2=\text{"B"} \mid t_1=\text{"A"}) = 1.0$ —occurs precisely because conditioning on the token "A" (not in $V^*$ ) restricts the possible continuations in a way that conditioning on the character "A" does not. The MPC algorithm, when properly applied after refactoring to a $V^*$ boundary, would correctly recover the probability $\alpha$ .

3.4.6 The Byte-Pair Correction (BPC) Algorithm for BPE

While MPE (used in WordPiece) has the property that token boundaries are greedy and deterministic given the string, BPE (used in Llama, GPT-2, and most modern LMs) has a different structure: merges are applied in a fixed priority order determined by the vocabulary's merge list, applied left-to-right. This means the MPC algorithm's recursive decomposition—which relies on the Pass step extracting exactly the first token of the continuation's MPE encoding—does not directly apply to BPE. The BPC algorithm (Algorithm 2, Appendix H) uses a different strategy: enumerate all valid token-level "cover encodings" of the query string and sum their probabilities.

Cover encodings (Definition H.2, Appendix H.1): Given a string $x_n^1$ , a cover encoding is a valid token sequence $t_k^1$ such that:

$t_k^1$ is valid (re-encoding its decoded form yields the same token sequence).
$x_n^1$ is a prefix of $\text{decode}(t_k^1)$ : the decoded tokens start with the query string.
The last token $t_k$ covers a part of $x_n^1$ : specifically, $x_n^i \in t_k$ for some $1 \leq i \leq n$ , meaning the last token spans the boundary between the query string and what follows, or covers a suffix of the query.

The set $\text{cover}(x_n^1)$ contains all such token sequences. Critically, Proposition H.5 (Appendix H.3) shows that these cover encodings form a partition of the event $S(x_n^1)$ (all strings starting with $x_n^1$ ):

$S(x_n^1) = \bigcup_{\vec{t} \in \text{cover}(x_n^1)} S(\vec{t})$

and the sets $S(\vec{t})$ are pairwise disjoint for different $\vec{t}$ . Therefore:

$P(x_n^1) = \sum_{\vec{t} \in \text{cover}(x_n^1)} P(\vec{t})$

What this means operationally: Instead of recursively decomposing the query (as MPC does), the BPC algorithm enumerates every possible way the string $x_n^1$ could be tokenized as part of a longer valid sequence, computes the probability of each tokenization using the LM, and sums them. The challenge is efficiency: naive enumeration over all possible tokenizations would be exponential.

The BPC enumeration strategy (Algorithm 2, Figure 5): The key insight is Corollary H.3 and Proposition H.6 (Appendix H.3): for any cover encoding $\vec{t} = t_k^1$ of $x_n^1$ , if you know where the last token $t_k$ starts within $x_n^1$ (say, it begins at character $x_{j+1}$ for some $j$ ), then the preceding tokens $t_{k-1}^1$ are uniquely determined—they must be exactly $\text{encode}(x_j^1)$ , the BPE encoding of the prefix up to that boundary. This is because BPE, like MPE, produces deterministic tokenizations: once the boundary of the last token is fixed, the encoding of everything before it is forced.

The BPC algorithm therefore iterates over possible start positions $j$ for the last token, from $j = n-1$ down to $0$ :

For each position $j$ , identify the set $B = \{t \in V \mid x_{j+1}^n \in \text{prefix}(\text{decode}(t))\}$ : all tokens whose decoded form starts with the suffix $x_{j+1}^n$ .
The preceding tokens are fixed: $t_{k-1}^1 = \text{encode}(x_j^1)$ .
The probability contribution from this boundary position is:

$P(t_{k-1}^1) \times \sum_{t \in B} P(t_k = t \mid t_{k-1}^1)$

where $P(t_{k-1}^1)$ itself is computed recursively using the same algorithm (it is the probability of the prefix string $x_j^1$ ), and the sum is the probability that the next token starts with the suffix, analogous to the Branch step in MPC.

Sum these contributions over all $j$ . The result is $P(x_n^1)$ .

Why this works: Each cover encoding has exactly one last token that intersects $x_n^1$ . By iterating over where that token begins, we cover all possible cover encodings without duplication. For a given $j$ , the branch set $B$ captures all tokens that could serve as the last token. The encoding before $j$ is forced to be $\text{encode}(x_j^1)$ by Proposition H.6—no other tokenization is valid, so no other tokenization has non-zero probability (by the BPE version of Proposition H.4, which is the analog of Proposition 2.3).

Complexity: The BPC algorithm makes $O(n \cdot M)$ LM calls in the worst case, where $n$ is the string length and $M$ is the maximum token length, because computing $P(x_j^1)$ for each $j$ may require recursive calls. The paper notes (Appendix H.4) that pretokenization boundaries (e.g., whitespace in BPE-based tokenizers like Llama's) can be exploited to identify when character and token conditioning are equivalent without needing the full BPC machinery, since tokens cannot cross whitespace boundaries.

BPE vs. MPE correction: The key structural difference is that MPE's greedy-leftmost-longest property enables the recursive Pass/Branch decomposition where exactly ONE token in $T_{\text{pval}}$ has non-zero probability. BPE's merge-priority-order property does not guarantee this, so the BPC algorithm uses the cover-encoding enumeration approach instead. However, the paper notes (Appendix H, Remark) that the BPC algorithm is more general—it also works for MPE—because the cover-encoding partition (Proposition H.5) holds for any deterministic encoding algorithm. The MPC algorithm is a more efficient specialization for MPE that exploits MPE's specific structure to avoid enumerating all boundary positions.

3.4.7 Summary: The Complete Correction Pipeline

Putting all components together, the complete procedure to compute $P(x_{n+1}^N \mid x_n^1)$ from a tokenized LM is:

Tokenize the prompt: $t_i^1 = \text{encode}(x_n^1)$ .
Find the $V^*$ boundary: Identify the largest index $k \leq i$ such that $t_k \in V^*$ . If none exists, use $k=1$ (assuming a start token in $V^*$ ). Let $x_{n_k}^1 = \text{decode}(t_k^1)$ .
Apply the refactoring: The desired probability equals $P(x_{n_k+1}^N \mid t_k^1) / P(x_{n_k+1}^n \mid t_k^1)$ .
Compute each term using the appropriate correction algorithm:
- For MPE: Use the MPC algorithm (Algorithm 1), which for each term makes at most $N - n_k$ sequential LM queries, each returning a full next-token distribution.
- For BPE: Use the BPC algorithm (Algorithm 2), which enumerates cover encodings by iterating over possible last-token start positions and recursively computing prefix probabilities.
Return the ratio.

Key design choices and their justifications:

$V^*$ -based refactoring rather than direct character-to-token conversion: Direct computation of $P(x_{n+1}^N \mid x_n^1)$ would require summing over all token sequences consistent with the character prompt, which is combinatorially explosive. The refactoring reduces the problem to computing token-conditioned probabilities where the conditioning event is well-defined.
Recursive decomposition (MPC) rather than enumeration (BPC) for MPE: MPE's greedy structure guarantees that exactly one token in the Pass case is possible, making recursion efficient and exact. Enumeration would work but would be unnecessarily expensive.
Cover-encoding enumeration (BPC) for BPE: BPE's merge-priority structure does not provide the single-token Pass property, but the deterministic nature of BPE encoding still allows efficient enumeration by scanning boundary positions.
Truncate-Renormalization rather than trusting softmax outputs: Neural LMs with softmax assign non-zero probability to invalid encodings, which would break the correctness of both algorithms. The TR procedure provably improves the model while making the correction exact.
No finetuning or weight access required: Both algorithms treat the LM as a black-box next-token oracle. This makes them applicable to any existing trained model without modification, addressing the practical limitation that most deployed models cannot be retrained.

4. Key Insights and Innovations

Innovation 1: Tokenization Bias Is Structural, Not Statistical — A Formal Distinction With Practical Consequences

The paper's most fundamental conceptual contribution is the demonstration that tokenization-induced sampling bias is not an approximation error that better training or larger models can fix — it is a structural property of the encoding algorithm itself that persists even for optimally trained models with infinite data. This distinction reorients the entire conversation about tokenization from an empirical question ("how much does tokenization hurt?") to a formal one ("what probability events does tokenization make inaccessible?").

Prior to this work, the dominant approach to tokenization problems was empirical: researchers trained bigger models, gathered more data, or fine-tuned with new vocabularies to mitigate observed failures in spelling sensitivity (Xue et al., 2022), arithmetic (Singh & Strouse, 2024), and cross-lingual fairness (Petrov et al., 2024). The implicit assumption was that these failures reflected insufficient training — that with enough capacity and data, a tokenized LM could learn to overcome tokenization artifacts. The paper proves this assumption is false in a precise sense through Proposition 2.3, which establishes that an optimally trained tokenized LM assigns exactly zero probability to entire regions of character-string space — specifically, any string whose tokenization would be invalid under the encoding algorithm. This is not a soft deficiency that diminishes with scale; it is a hard constraint on what probability distributions a tokenized model can represent through its standard interface. The Markov chain example in Section 2.2 crystallizes this: when the prompt ends with a token not in V*, the model is forced to assign probability 1.0 to certain continuations regardless of the true data distribution, because the encoding structure eliminates the competing possibility from the conditioning event.

What makes this move intellectually distinctive is that it reframes tokenization bias as an interface problem rather than a learning problem. The model's weights do implicitly contain character-level information — the information is there, learned from the tokenized training data — but the standard next-token API that models expose does not give you direct access to it. The bias arises from incorrectly mapping between character-conditioned and token-conditioned events, not from any failure of the model to learn the underlying distribution. This reframing has immediate implications: if the model has the information but the interface is wrong, the solution is to change how you query the model, not to retrain it. This is exactly what the correction algorithms accomplish — they rewrite character-level queries into token-level queries whose answers, when properly combined, recover the character-level distribution. This is a fundamentally different intellectual approach from prior work that either tried to eliminate tokenization (token-free models) or adapt it through retraining (vocabulary transfer). The paper identifies a new category of solution: inference-time probabilistic correction that treats the encoding algorithm as a known transformation to be inverted.

The significance extends beyond the specific correction algorithms. The concept of invalid encodings as the mechanism producing bias provides a diagnostic tool for analyzing any tokenization scheme. One can examine a vocabulary and encoding algorithm and identify, a priori, which conditioning events will produce bias and which will not, without running a single experiment. This shifts tokenization analysis from post-hoc empirical debugging to formal verification.

Innovation 2: The V* Criterion as a Bridge Between Token and Character Domains

The identification of V* — the set of tokens that cannot appear as substrings of any other token — as the precise condition under which character and token conditioning events become equivalent is a deceptively simple insight with deep theoretical consequences. Before this paper, the relationship between character strings and their tokenizations was understood operationally (encode, decode) but not probabilistically. The paper provides the first formal characterization of when conditioning on a token sequence and conditioning on its decoded character string describe the same event, and when they diverge.

Proposition 3.1 establishes that for any token history ending in a V* token, the sets of possible strings are identical — the token boundary is immutable, so knowing the tokens tells you exactly the characters, and knowing the characters tells you exactly the tokens. This bidirectional equivalence is what enables the clean substitution in Corollary 3.2: P(characters | tokens) = P(characters | characters) when the token is in V*. When the last token is NOT in V* — which is the common case for tokens that can be merged into longer units — the sets diverge, and bias occurs.

What distinguishes this contribution is its generality. The V* property depends only on the vocabulary structure, not on the model weights, training data, or even the specific encoding algorithm. For any vocabulary and any deterministic encoding scheme, you can compute V* by substring matching, and the resulting tokens are guaranteed to produce stable character-token equivalence. This transforms a problem that appeared to require per-model empirical calibration into one that can be solved by examining the vocabulary file alone.

The practical consequence — which the paper demonstrates but whose implications extend beyond the current experiments — is that any tokenized LM can be made to reveal its character-level knowledge, provided you know how to navigate the V* boundaries. This means the vast ecosystem of pretrained tokenized models can, in principle, be used as if they were token-free, without retraining or weight modification, provided someone implements the correction algorithms. The V* criterion is the theoretical key that unlocks this capability. The paper notes (Section 3.1, footnote) that most current LMs already include start tokens in V*, meaning the bridge between domains exists in every deployed model — it simply was not recognized or exploited before this work.

Innovation 3: The Truncate-Renormalization Argument — Proving That Enforcing Zero Probabilities Improves Models

A standard intuition in machine learning is that softmax-based models should be left as-is because their probability assignments, while never exactly zero, represent calibrated uncertainty that training optimized. The paper presents a counterintuitive result that challenges this intuition: explicitly zeroing out certain next-token probabilities and renormalizing produces a model that is provably closer to the ground truth in KL divergence, as measured by lower token-level perplexity (Proposition G.1, Appendix G).

The argument is elegant in its simplicity and generality. Given any target distribution p where some events have true probability zero, and any approximation q with strictly positive probabilities (as softmax forces), setting q's probabilities to zero on those zero-true-probability events and renormalizing always reduces KL(p || q). The proof requires only that the normalizing constant Z ≤ 1, which is true because we sum over a subset of the original probabilities. The perplexity reduction follows directly since cross-entropy decomposes into entropy plus KL divergence.

This result is significant for two reasons beyond its immediate application to the correction algorithms. First, it provides a theoretical justification for post-hoc probability modification that contradicts the folk wisdom that softmax outputs should be trusted as-is. The paper shows not just that TR doesn't hurt, but that it provably helps — the modified model is mathematically guaranteed to be a better approximation of the data-generating process. Second, it transforms the invalid-encoding problem from a nuisance (something the correction algorithm has to work around) into a feature (something that, when properly handled, improves the model). The fact that TR-modified LMs have lower perplexity means that enforcing the encoding structure is not merely a compatibility hack for the correction algorithms — it is a model improvement in its own right.

Prior work on model calibration and post-hoc correction (temperature scaling, Platt scaling) focused on adjusting probabilities to match empirical frequencies. The TR argument is fundamentally different: it adjusts probabilities to match logical constraints imposed by the encoding algorithm, constraints that are true by construction of the training data rather than estimated from finite samples. This connects tokenization correction to the broader literature on constrained probabilistic inference, where imposing known structural zeros improves estimates.

The negative implication is equally important: any tokenized LM that does NOT enforce these structural zeros is, in a precise sense, miscalibrated — it assigns probability mass to events that can never occur in its own training distribution. The paper's TR procedure provides a principled remedy that can be applied to any existing model without retraining.

Innovation 4: Reconciling Tokenized and Token-Free Modeling — Statistical Equivalence Without Architectural Change

The paper's most ambitious conceptual claim, stated explicitly in the introduction and supported by the theoretical framework, is that tokenized and token-free LMs are statistically equivalent — the same underlying character-level distribution is learned in both cases, just accessed through different interfaces. This is not an empirical claim about current model performance (token-free models lag behind tokenized ones, as the paper acknowledges from Yu et al., 2024), but a theoretical claim about what information is present in the model weights.

The significance of this claim becomes clear when viewed against the landscape of prior work. The field has treated tokenized and token-free modeling as competing paradigms with different trade-offs: tokenized models achieve better efficiency and performance through compression, while token-free models avoid tokenization artifacts at the cost of longer sequences and worse scaling. This framing implies that choosing one paradigm means accepting its limitations — if you want token-free behavior, you must train a token-free model.

The paper's equivalence claim breaks this dichotomy. If a tokenized LM implicitly learns the token-free distribution, then token-free behavior can be extracted from tokenized models through appropriate probabilistic queries. The correction algorithms are not approximating token-free behavior or learning it from data — they are revealing what the model has already learned but cannot express through its standard next-token interface. This reframes tokenization not as something that limits what models can learn, but as something that limits what queries the standard API can answer correctly. The model's knowledge is complete; the interface is not.

The empirical validation in Section 4, while on a small-scale Markov chain experiment, demonstrates the principle: the correction algorithms recover the exact ground-truth transition probabilities that the baseline token-querying approach distorts. The baseline's errors are not random noise or approximation artifacts — they are deterministic distortions produced by the encoding structure (e.g., outputting probability 1.0 where the truth is α). The correction undoes these distortions exactly, recovering the character-level probabilities the model absorbed from tokenized training data.

This insight has direct implications for model evaluation, transfer, and deployment that the paper flags but does not fully explore. Character-level perplexity can be computed from tokenized LMs using the correction, providing a more principled metric that doesn't confound tokenization quality with model quality. Models trained with different vocabularies can, in principle, be compared on the same character-level ground without retraining either one. And the entire ecosystem of deployed tokenized models — which represents an enormous investment in pretraining compute — can potentially be repurposed for token-free-style applications through inference-time correction alone. These implications remain speculative without larger-scale validation, but the theoretical foundation the paper provides makes them plausible research directions rather than wishful thinking.

5. Experimental Analysis

Evaluation Methodology

Dataset. All experiments use a synthetically generated dataset from a 3rd-order Markov chain over the alphabet A = {"A", "B"}, where the transition matrix is randomly constructed. The paper generates training data by sampling strings from this Markov chain and then tokenizing them using the specified vocabulary and encoding algorithm (MPE or BPE). For MPE experiments, the vocabulary is V = {"A", "B", "AA", "BAAB", "BBAA", "BBBA", "BA", "BBA"}. For BPE experiments (Appendix H.4), the vocabulary is V = {"A", "B", "B·A", "BA·A", "B·BAA", "A·A", "BA·BA", "B·B"}, where the order within V determines the merge priority and "·" separates the merging tokens. The paper does not use a standard benchmark dataset (e.g., MATH, HumanEval); instead, it constructs a controlled synthetic environment where the ground-truth character-level transition probabilities are known exactly, which is essential for verifying whether the correction algorithms recover unbiased estimates.

Base model. The LM is trained from scratch using a GPT-2 architecture with 6 hidden layers. Hyperparameters beyond the layer count are not specified (no learning rate, batch size, optimizer, or training tokens are reported). The model is trained on tokenized sequences generated from the Markov chain, meaning it sees only token-level data and optimizes the standard next-token prediction objective. The choice of this architecture and scale is not explicitly justified, but it appears designed to be "representative" of autoregressive transformer LMs while being small enough for controlled experiments where the ground-truth distribution is known. The paper notes (Appendix A) that, unlike Makkuva et al. (2024), it "does not observe" transformers struggling to learn 2nd-order Markov chains, implying the model successfully learns the token-level distribution.

Metrics. The primary metric is the probability of the next character being "A" given the previous three characters, i.e., P(x_{n+1} = "A" \mid x_n^{n-2}), where x_n^{n-2} is a specific 3-character state among the 2^3 = 8 possible states ("AAA", "AAB", ..., "BBB"). This is a pointwise probability estimate, not an accuracy or loss metric. The ground truth is the known transition probability from the Markov chain's construction. The paper averages probability estimates over 100 runs with different context lengths while fixing the last 3 characters, which controls for the Markov chain's 3rd-order property (the next character depends only on the previous three, regardless of total context length). Results are displayed as bar charts in Figure 3 (MPE) and Figure 7 (BPE, Appendix H.4) comparing three quantities for each of the 8 input states: the ground-truth probability, the paper's corrected estimate, and the baseline estimate.

Baselines. The paper compares against a single baseline, referred to as P(x_{n+1} \mid t_i^1), which is described as "the conventional method of directly prompting tokens into the language model" (Section 1) and equivalently as "one Branch step in the MPC algorithm" (Section 4). Operationally, this baseline: (1) encodes the prompt string x_n^1 into tokens t_i^1 = encode(x_n^1); (2) queries the LM for the next-token distribution P(t_{i+1} \mid t_i^1); (3) sums the probabilities of all tokens whose decoded form starts with the target character (e.g., for target "A", it sums over tokens like "A", "AA", "AAB", etc.). This is the "naïve" character-level inference that a practitioner would naturally perform, and it is exactly what Definition 2.1 identifies as the source of bias when P_{\text{gt}}(x_{n+1} \mid x_n^1) \neq P_{\text{gt}}(x_{n+1} \mid t_i^1). No other baselines are compared (e.g., no token-free model, no fine-tuned vocabulary adaptation, no stochastic tokenization).

Generation budget / compute accounting. Since this is a probability estimation task rather than a generation task, the relevant compute measure is the number of model forward passes required to compute a single probability estimate P(x_{n+1} \mid x_n^{n-2}). The baseline requires exactly one forward pass (one call to the LM for the next-token distribution). The MPC algorithm's cost is not explicitly measured in the experiments, but the paper states (Section 3.2) that complexity "scales with the length of the query string, i.e., N - n_k" forward passes, where each recursive call consumes one LM run. For the 3rd-order Markov experiment, the query string length is 1 character (just the next character), so the MPC algorithm would require at most 1 recursive call—making its cost comparable to the baseline in this specific setting. The BPC algorithm's cost is higher in general (O(n · M) where M is the maximum token length, Appendix H.3), but for single-character queries it may also be modest. The paper does not report wall-clock times or FLOP counts for either method.

Cross-validation / statistical protocol. No cross-validation or train/test splitting of the Markov chain is described. The ground-truth transition matrix is known by construction, so the evaluation is effectively a comparison of estimation methods against known parameters rather than generalization to held-out data. The 100-run averaging across different context lengths serves as a variance-reduction technique rather than a statistical validation protocol—it ensures that the probability estimates are not idiosyncratic to a particular prompt length. Standard errors or confidence intervals are not reported for the bar heights in Figures 3 and 7.

Main Quantitative Results

Recovery of Markov Chain Transition Probabilities Under MPE

Headline result. Figure 3 (Section 4, main paper) shows that across all 8 possible 3-character input states ("AAA" through "BBB"), the paper's MPC-based correction method produces next-character probability estimates that closely match the ground-truth transition probabilities, while the baseline method exhibits large and systematic distortions for specific states. The magnitude of the baseline's errors is not uniform: for some states it nearly matches the ground truth, while for others it is catastrophically wrong—in one case outputting probability 1.0 for a character whose true probability is visibly different (recall from the Markov chain example in Section 2.2 where the baseline outputs P(B \mid t_1 = "A") = 1.0 while the true value is α).

State-by-state patterns in Figure 3. Interpreting the bar chart (Figure 3, main paper):

The x-axis lists the 8 possible input states ("AAA", "AAB", ..., "BBB"). For each state, three bars are shown representing the ground-truth probability that the next character is "A", the paper's corrected estimate, and the baseline estimate.
States where the baseline is accurate: For several states, the baseline and the correction both match the ground truth. Based on the pattern visible in the figure and the theory, these would be states where the prompt's encoding ends with a token in V^* (e.g., if the last token is "AA" or "B" in the MPE vocabulary, since Proposition 3.1 guarantees equivalence in these cases). The paper does not enumerate which states fall into this category, but the theoretical framework predicts it.
States where the baseline fails: For the problematic states (those whose encoding ends with a token not in V^*, such as "A" when "AA" exists), the baseline shows substantial deviation from ground truth. The corrected estimates for these same states closely track the ground truth, typically matching it within the resolution visible in the bar chart.
Zero-probability events in the baseline: The paper notes (Section 4) that "following Proposition 2.3, one can clarify the zero probability events output from the baseline estimator." This refers to states where the baseline outputs exactly 0.0 or 1.0 for the next-character probability—which Proposition 2.3 predicts will occur when the conditioning token sequence creates an encoding constraint that eliminates certain character continuations from the model's accessible probability space. The correction method recovers non-degenerate probabilities for these states.

Quantitative precision. The paper does not report numerical values for the bar heights, root-mean-square error, or any other quantitative metric comparing corrected estimates to ground truth. The evaluation is purely visual: Figure 3 shows bars that appear to match, and the text states that the method "accurately estimates the ground truth probability." The degree of match appears close—the corrected bars align with the ground-truth bars within what is visually discernible—but without tabulated numbers or error metrics, the claim of accuracy remains qualitative.

Comparison to the baseline's failure modes. The baseline does not fail uniformly. For some input states, its bar is indistinguishable from the ground truth. This is consistent with the theory: when the tokenization of the 3-character state ends with a V^* token, the character-level and token-level conditioning events coincide (Corollary 3.2), and the baseline's naïve marginalization is actually correct. The baseline only fails for states where the encoding produces a conditioning token that is not in V^*, which is exactly the scenario where Proposition 3.1 shows S(t_i^1) \subset S(x_n^1) but not vice versa—the token conditioning restricts the possible continuations beyond what the character conditioning would restrict, producing the bias.

Recovery of Markov Chain Transition Probabilities Under BPE

Headline result. Figure 7 (Appendix H.4) replicates the same experiment using BPE encoding with the specified merge-priority vocabulary. As with MPE, the paper's correction method (BPC algorithm) accurately recovers the ground-truth next-character probabilities across all 8 states, while the baseline exhibits significant bias for certain states. The paper states (Appendix H.4): "our method can accurately recover the ground truth probability P(x_{n+1} \mid x_n^1) while the baseline fails to."

Notable difference from MPE results. The paper highlights one specific state where the BPE baseline performs differently from what might be expected: "for the state 'BAA', the baseline approach can output the correct probability, which is because the merging for the token 'BAA' happens before any merges where 'A' is the left token happens." This is a subtle observation about BPE's merge-order dependency. In BPE, the encoding of "BAA" depends on the merge priorities. Because the merge creating "BAA" occurs before merges involving "A" as the left token, the tokenization of strings starting with "BAA" is stable in a way that avoids the bias that would otherwise occur. This illustrates that while both MPE and BPE induce bias, the specific pattern of which states are affected depends on the encoding algorithm's structure and vocabulary composition. The paper's theoretical framework (invalid encodings, V^*) captures both cases, and the correction algorithms handle both correctly.

Quantitative reporting. As with the MPE experiment, no numerical values, error metrics, or confidence intervals are reported. The evaluation is visual comparison of bar charts in Figure 7.

Ablation Studies and Robustness Checks

The paper contains no dedicated ablation experiments in the conventional sense. There are no experiments that:

Vary the vocabulary size or composition to test sensitivity of the correction to vocabulary design.
Compare the MPC and BPC algorithms on the same MPE task (despite acknowledging BPC works for MPE—Appendix H, Remark).
Measure computational cost (wall-clock time, memory, or FLOPs) of the correction algorithms versus the baseline.
Test on higher-order Markov chains (4th, 5th order) to assess scaling with context length.
Test on non-Markov data or natural language to assess real-world applicability.
Compare against alternative correction methods (e.g., stochastic tokenization, vocabulary adaptation) to demonstrate that the proposed approach is preferable to existing heuristics.
Vary the model architecture or scale to test whether the bias and correction generalize beyond the specific 6-layer GPT-2 setup.
Report results with and without the Truncate-Renormalization procedure to assess its practical impact on correction accuracy.
Measure the perplexity improvement from TR to validate Proposition G.1 empirically.

BPE vs. MPE comparison (implicit ablation): The paper runs separate experiments for MPE (Figure 3) and BPE (Figure 7, Appendix H.4) with different vocabularies but the same Markov chain and model architecture. This functions as an implicit ablation over encoding schemes: it demonstrates that the correction framework handles both encoding families correctly, and that the specific bias patterns differ between them. The BPE experiment also implicitly validates the cover-encoding enumeration strategy against the recursive decomposition strategy, though no direct comparison of the two algorithms on the same task is conducted.

Baseline as ablation of the correction: The primary comparison—baseline vs. corrected—can be viewed as an ablation of the correction itself. The baseline represents the MPC algorithm with only the Branch step (no Pass step, no recursion, no refactoring to a V^* boundary). The fact that the baseline fails while the full algorithm succeeds demonstrates that the Pass step and the V^*-based refactoring are both necessary components—removing either would break the correction. However, the paper does not present intermediate ablations that isolate which components are individually responsible for which gains (e.g., refactoring without the full MPC recursion, or MPC without refactoring).

Negative result from ReST^EM (Appendix K): While not an ablation of the correction algorithms per se, Appendix K describes an attempt to improve the revision model using the ReST^EM method (Singh et al., 2024), which "backfires: additional sequential revisions substantially hurt performance." The paper hypothesizes that "on-policy data collection in ReST^EM exacerbates spurious correlations in revision data, causing the model to fail to learn the revision task properly." This is a genuine negative result demonstrating sensitivity of revision training to data generation methodology. However, this ablation belongs to a different line of investigation (revision models) that is only mentioned in passing in this paper's appendix; the main correction algorithms have no analogous sensitivity analysis.

Critical Assessment

The experiments demonstrate a clear and important phenomenon: tokenization induces a sampling bias in next-character probabilities, and the proposed correction algorithms can recover unbiased estimates in a controlled synthetic setting. However, the experimental evidence is minimal and leaves substantial gaps between what is demonstrated and what the paper's broader claims require.

What the experiments actually show:

For a specific 3rd-order Markov chain over a binary alphabet, with a specific hand-crafted vocabulary, and a specific 6-layer GPT-2 model trained from scratch, the MPC and BPC algorithms produce next-character probability estimates that visually match the ground truth, while the naïve baseline produces visibly biased estimates for some (but not all) input states. This is demonstrated in two bar charts (Figures 3 and 7) with no reported numerical error metrics, statistical tests, or confidence intervals.
The bias exists in both MPE and BPE encoding schemes, and the correction handles both, though the specific states affected differ between the two.

What the experiments do not show:

Scale to realistic settings. The gap between a 3rd-order binary Markov chain with 8 possible states and natural language with vocabularies of tens of thousands of tokens and context lengths of thousands is enormous. The paper's central claim—that the correction enables "token-free behavior from a tokenized LM"—is demonstrated only for a toy problem where the ground truth is a known 3rd-order Markov chain. Real language has much higher-order dependencies, vastly larger state spaces, and unknown ground-truth distributions. The algorithms' correctness proofs are general (they do not depend on the Markov assumption), but their practical behavior at scale—both in terms of computational cost and numerical stability—is completely untested. The MPC algorithm's complexity is O(N - n_k) model forward passes for a query of length N - n_k characters; for a typical natural language continuation prediction (e.g., the next 10 characters), this could mean 10 sequential model calls, but for longer continuations the cost could become prohibitive. The paper provides no empirical timing or cost data.

Model scale and training regime. The experiments use a 6-layer GPT-2 trained from scratch on the specific Markov data. Real deployed LMs are orders of magnitude larger, pretrained on heterogeneous corpora, and may exhibit different calibration properties. Proposition 2.3 assumes an "optimally trained" LM—one that exactly learns the training distribution. Real LMs are not optimally trained; they are approximations with softmax outputs that assign non-zero probability to invalid encodings. The TR procedure (Appendix G) is guaranteed to improve token-level perplexity while enforcing the zero-probability constraints, but this guarantee is theoretical (KL divergence bound) and its empirical effect on correction accuracy in realistic models is not measured. Would TR applied to a production Llama model noticeably change its outputs? Would the correction algorithms work correctly without TR on real models where softmax assigns small but non-zero probabilities to invalid encodings? These questions are not addressed.

Vocabulary sensitivity. The correction algorithms depend on the vocabulary structure (computing V^*, enumerating cover encodings, checking encoding validity). The experiments use small, hand-crafted vocabularies with 5–8 tokens. Real vocabularies (e.g., Llama's 32K tokens, GPT-4's 100K tokens) have much more complex substring relationships. An ablation varying vocabulary size, composition, or merge order would demonstrate that the algorithms work across the range of practical vocabularies, but no such experiment exists. The single observation about the BPE state "BAA" being accurate due to merge-order timing is intriguing but only scratches the surface of BPE's behavioral complexity.

Comparison to alternative approaches. The paper positions itself against token-free models, vocabulary adaptation, and stochastic tokenization, but none of these are compared empirically. The only baseline is the naïve token-querying approach. While the correction beats this baseline on the toy problem, it is unknown whether simpler heuristics—such as always padding prompts to end at whitespace boundaries, using BPE-dropout at inference, or applying rule-based adjustments to the most common bias cases—would achieve comparable practical improvements with lower computational cost. The paper's theoretical contribution is strong, but the empirical case for its practical superiority over alternative correction strategies is absent.

Lack of quantitative rigor in results reporting. Figures 3 and 7 present bar charts without numerical values, statistical tests, or error metrics. Claims like "Our method, in contrast, accurately estimates the ground truth probability" are supported only by visual inspection. In a paper whose primary contribution is an algorithm for removing bias, one would expect quantitative measures of residual bias after correction—e.g., maximum absolute error, root-mean-square error, or KL divergence between corrected estimates and ground truth—reported in a table. Their absence makes it impossible to assess whether the correction is exact (as the theory predicts for optimally trained models), approximate (due to model suboptimality), or somewhere in between.

The revision model experiments (Appendix K) are tangential. The ReST^EM failure in Appendix K relates to an entirely different topic (self-improving revision models) that appears disconnected from the main tokenization correction narrative. It demonstrates fragility in a different component but does not validate or stress-test the core correction algorithms.

Missing ablation: direct measurement of the bias magnitude. The paper defines the next-character sampling bias (Definition 2.1) formally but never quantifies it empirically beyond the bar charts. How large is the discrepancy |P_{\text{gt}}(x_{n+1} \mid x_n^1) - P_{\text{gt}}(x_{n+1} \mid t_i^1)| across the state space? Does it correlate with measurable properties of the vocabulary (e.g., token length, frequency in training data, V^* membership)? An analysis of the bias's structure would strengthen the motivation for correction and help practitioners identify when the bias is likely to be severe enough to warrant the computational cost of correction.

The central empirical claim is narrow but internally valid. The experiments do convincingly demonstrate that tokenization bias exists (the baseline is wrong) and that the proposed algorithms can correct it (the corrected estimates match ground truth) for the specific tested configuration. This is a genuine and non-trivial result—showing that the bias is not merely theoretical but manifests in practice and is algorithmically reversible. However, the paper's broader implications—that the method enables computing character-level perplexity from any tokenized LM, simulating token-free behavior, and transferring between vocabularies without finetuning—are supported only by the theory and the toy experiment. These implications may well be true, but the experimental evidence does not yet demonstrate them at any scale resembling practical deployment. The paper would be substantially strengthened by experiments on a standard language modeling benchmark (e.g., character-level perplexity on WikiText-2 with a pretrained GPT-2 or Llama checkpoint) showing that the correction produces different (and presumably better) estimates than the baseline, or that TR actually reduces token-level perplexity on real data as Proposition G.1 predicts.

6. Limitations and Trade-offs

1. The Difficulty Estimation Cost Is Unaccounted for and Potentially Prohibitive

The assumption or constraint. The entire compute-optimal scaling framework depends on estimating prompt difficulty before allocating the inference budget. The paper's proposed method for difficulty estimation—generating 2048 samples per question and averaging the PRM's final-answer scores (or the ground-truth correctness, for oracle bins)—is extraordinarily expensive relative to the test-time compute budgets being optimized. The paper explicitly acknowledges this gap in Section 3.2:

"estimating difficulty in this way still incurs additional computation cost during inference... our experiments do not account for this cost largely for simplicity"

The 2048-sample cost is, by itself, 8× the largest test-time budget studied (256 generations) and 32× the budget at which the 4× efficiency gains are claimed (64 generations). The paper's complexity analysis (Section 3.2) frames difficulty estimation as an exploration-exploitation tradeoff and flags it as "a key avenue for future work," but provides no algorithm or cost model for amortizing or reducing this overhead.

The consequence. The reported 4× efficiency gains over best-of-N—the paper's headline practical result—are computed assuming difficulty is already known at zero cost. In any realistic deployment, the total inference cost is difficulty estimation plus strategy execution. The former could easily dominate the latter, erasing or reversing the claimed savings. A practitioner deploying compute-optimal scaling would face a stark choice: pay the full 2048-sample cost to estimate difficulty (making the total cost much higher than uniform best-of-N at any budget) or use a cheaper but less accurate difficulty proxy (risking suboptimal strategy selection that degrades the 4× gain). Without a cost-effective difficulty estimator, the compute-optimal framework remains a conceptual contribution rather than a deployment-ready system.

What evidence exists in the paper. Figures 4 and 8 show that compute-optimal scaling with predicted difficulty bins (using the PRM's average score from 2048 samples) closely tracks oracle difficulty bins (using ground-truth labels from 2048 samples). This demonstrates that the PRM-based difficulty proxy works—it recovers difficulty without needing answers—but it does not address the cost of computing the proxy. The predicted difficulty curves in Figures 4 and 8 are generated using the full 2048-sample PRM score average, so there is no evidence in the paper about how accuracy degrades with fewer samples. The paper does not report an ablation varying the number of samples used for difficulty estimation, nor does it measure whether a small number of samples (e.g., 4, 8, 16) suffices to bin questions accurately. A practitioner cannot determine from the paper whether estimating difficulty from, say, 16 samples would preserve most of the 4× gain or collapse it entirely.

Mitigation status. The paper does not attempt to reduce the difficulty estimation cost. Section 8 flags "pretraining or finetuning models to directly predict difficulty of a question" as future work, and Section 3.2 acknowledges the exploration-exploitation tradeoff as an open problem. No experiments test lightweight difficulty proxies, adaptive sampling schemes, or models that predict difficulty from question text alone. The limitation is clearly stated by the authors but completely unresolved in the current work.

2. Single Benchmark and Single Model Family Preclude Assessing Generality

The assumption or constraint. All experiments use the MATH benchmark (500 test questions from the Lightman et al., 2022 split) with PaLM 2-S* as the base model. The paper justifies the model choice in Section 4 by stating that PaLM 2-S* is "representative of the capabilities of many contemporary LLMs" and sits in a regime with "non-trivial performance on MATH (roughly 10–19% pass@1 depending on the prompt and sampling configuration) but far from saturation." No experiments are conducted on other model families (GPT, Llama, Gemini, Claude), other benchmarks (code generation, logical reasoning, scientific QA), or other tasks requiring different reasoning types.

The consequence. Several aspects of the paper's findings could be model-specific or benchmark-specific in ways that affect their practical applicability:

The PRM's quality and over-optimization behavior depend on PaLM 2-S*'s output distribution—its calibration, its error patterns, and the degree to which its internal representations support step-level value prediction. A model with different training data, architecture, or scale might exhibit completely different over-optimization thresholds, changing which search algorithms are optimal at which budgets.
The revision model's scalability depends on PaLM 2-S*'s in-context learning capabilities and the quality of the edit-distance-based training data. Models with different in-context learning behaviors or different response styles might not learn revisions as effectively from the same data construction procedure.
The MATH benchmark consists of high-school competition math problems requiring symbolic multi-step reasoning, typically with a single correct answer. It is unclear whether the difficulty-dependent patterns (beam search hurting easy problems, revisions helping easy problems, nothing helping hard problems) generalize to code generation (where correctness is multi-faceted), open-ended generation (where there is no single right answer), or factual QA (where the bottleneck is knowledge retrieval rather than reasoning).
The optimal strategy per difficulty bin, selected via cross-validation on the MATH test set, is likely specific to this benchmark's difficulty structure. Transferring the policy to another task would require re-estimating the optimal strategies on that task's data.

What evidence exists in the paper. The paper provides no cross-model or cross-benchmark results. All Figures (3–9) and all ablations (Appendices E–M) are from PaLM 2-S* on MATH. The authors acknowledge the single-model limitation implicitly in Section 4 by stating they "believe" the model is representative, but this belief is not tested. The paper's very finding—that difficulty-dependent strategy selection is essential—ironically implies that the optimal policies themselves are difficulty-distribution-dependent and therefore task-dependent, yet no evidence confirms that the qualitative patterns (beam search > best-of-N on medium problems, etc.) transfer.

Mitigation status. Not addressed. The paper does not claim generality beyond MATH and PaLM 2-S*, but the framing throughout (e.g., Section 1: "To counter this universal problem...") implies broader applicability. Section 8 does not explicitly call for cross-benchmark replication, focusing instead on extensions of the method itself (combining search with revisions, cheap difficulty estimation, dynamic policies). A practitioner considering deploying compute-optimal scaling on, say, a code generation task with a Llama model cannot determine from this paper whether the approach would work, how to adapt the strategies, or even whether the same difficulty-dependent patterns would hold.

3. The ~14× Larger Model Baseline Is Not Compute-Optimally Trained and Uses Only Greedy Decoding

The assumption or constraint. The FLOPs-matched comparison in Section 7 compares PaLM 2-S* with compute-optimal test-time scaling against a model with approximately 14× more parameters, trained with the same amount of data (scaling parameters only, not data). The larger model uses only greedy decoding—no majority voting, no best-of-N, no beam search, no revisions. The paper explicitly acknowledges the parameter-only scaling departure from compute-optimal pretraining (Hoffmann et al., 2022) in Section 7:

"We choose this setting as it is representative of a canonical approach to scaling pretraining compute and leave the analysis of compute-optimal scaling of pretraining compute where the data and parameters are both scaled equally to future work."

The paper also notes that this follows the LLaMA paradigm (Touvron et al., 2023) rather than Chinchilla-optimal scaling.

The consequence. The reported advantages of test-time compute over pretraining are measured against a weakened baseline in two ways:

Non-optimal training: A Chinchilla-optimal model trained with 14× more total FLOPs would scale both parameters and data according to the established N ∝ C^0.5, D ∝ C^0.5 relationship. Fixing data and scaling only parameters means the larger model is over-parameterized for its data budget, potentially underperforming a properly scaled model at the same FLOP count. The reported +27.8% relative improvement from test-time compute on easy questions at R ≪ 1 (Figure 1 bar chart) could shrink or reverse against a Chinchilla-optimal larger model.
No test-time compute for the baseline: The larger model uses greedy decoding with zero additional inference compute. A fairer comparison would give the larger model some test-time compute budget as well—perhaps a smaller budget, since the paper's central claim is that test-time compute is more efficient than pretraining, not that pretraining provides zero benefit. If the 14× larger model with best-of-8 or best-of-16 already matches or exceeds the compute-optimal small model's performance, the practical case for test-time compute over pretraining weakens substantially for all but the most compute-constrained deployments.

The paper's findings are most reliable as a demonstration that test-time compute can substitute for some amount of pretraining compute under specific conditions, not as a precise calibration of the tradeoff ratio. The claim that a smaller model with test-time compute can "outperform a ~14× larger model" (Section 7, Figure 1) is technically correct for the specific baseline chosen but overstates the practical advantage relative to what a well-optimized larger model could achieve.

What evidence exists in the paper. The FLOPs comparison is detailed in Section 7 and Figure 9, with the three R values (0.16, 0.79, 22) and the corresponding budget multipliers. The paper transparently states both caveats (parameter-only scaling, greedy decoding for the baseline). The strength of the evidence is that it establishes a lower bound on test-time compute's substitutability—even against this weakened baseline, test-time compute only wins on easy-to-medium problems at low R—and the paper is appropriately cautious about generalization. The sharper boundaries (failure on hard problems at all R, failure at high R even for medium problems) are likely robust to baseline improvements.

Mitigation status. Partially addressed via transparency, but not experimentally. The paper acknowledges both limitations explicitly and flags Chinchilla-optimal pretraining comparisons as future work. No experiments test the larger model with its own test-time compute budget, even though this would directly address the fairness concern. A practitioner reading this paper should interpret the 14× figure as an upper bound on the substitution ratio and expect that, against a properly optimized large model with some inference computation, the effective substitution ratio is smaller.

4. The Revision Model Suffers from a 38% Correct-to-Incorrect Reversion Rate and Training Fragility

The assumption or constraint. The revision model is trained on sequences where all in-context answers are incorrect followed by a correct answer, using edit-distance-based pairing of independently sampled responses (Section 6.1). This means the model never sees examples where the current answer is already correct and should be preserved. At inference time, as the revision chain grows, the model may encounter correct answers in its context and incorrectly "revise" them to wrong answers. The paper reports (Section 6.1) that "approximately 38% of correct answers get converted back to incorrect ones" under naïve sequential revision.

The consequence. The revision model has a fundamental instability: each round of revision has a non-trivial probability of degrading an already-correct answer. The paper mitigates this by using majority voting or verifier-based selection across the entire revision chain (Section 6.1), treating all revisions as candidates and selecting the best one rather than always taking the last revision. This patch works—Figure 6 (left) shows pass@1 gradually improving over the chain, and Figure 6 (right) shows that sequential revisions with verifier selection outperform parallel sampling—but it does not solve the underlying problem:

Inefficient budget usage: If ~38% of correct answers are being reverted, a substantial fraction of the sequential revision budget is wasted generating degraded versions of already-good solutions rather than refining actually-incorrect ones.
Requires a verifier: The mitigation depends on having a reliable verifier to select the best answer from the chain. If the verifier shares the revision model's biases, it may select a degraded answer over a correct earlier revision. The paper notes (Appendix J) that the PRM trained on base model outputs does not transfer well to revision model outputs, requiring a separate revision-specific ORM.
Training fragility: Appendix K demonstrates that attempting to optimize the revision model with ReST^EM (on-policy RL-based training) causes performance to substantially degrade with sequential revisions. This suggests the revision training procedure is sensitive to data generation methodology in ways that are not fully understood, and the paper's positive results depend on specific offline data construction choices that may not transfer.

What evidence exists in the paper. The 38% reversion rate is explicitly stated in Section 6.1. Figure 6 (left) shows the pass@1 trajectory over 64 sequential steps, which rises from ~18% to ~24% and then fluctuates, consistent with a dynamic where new correct answers are produced but some existing correct answers are lost. The ReST^EM failure is shown in Appendix K, Figure 16, where fully sequential performance drops to ~33.5% compared to ~38.5% at the optimal ratio. The paper does not report an ablation that removes the edit-distance-based pairing or tests alternative training data construction methods for the revision model.

Mitigation status. Partially mitigated via within-chain selection (majority voting or verifier), but the core problem—the model was not trained to preserve correctness—persists. The paper does not experiment with training the revision model on mixed trajectories (some with correct in-context answers that should be kept unchanged), nor with inference-time heuristics (e.g., stopping revision when the verifier score stops improving). Section 8 does not mention the reversion problem or training fragility as future work, focusing instead on combining revisions with PRM tree-search and cheap difficulty estimation. A practitioner building a revision-based system should expect to invest in verifier quality (to filter out degraded answers) and should be cautious about further optimizing the revision model beyond the paper's offline SFT procedure.

5. The Hardest Problems Remain Completely Unsolved—Test-Time Compute Cannot Create Capability

The assumption or constraint. The paper's framework assumes that the base model has non-zero capability on a problem—that the proposal distribution contains at least some correct solutions. This is implicit in the compute-optimal formulation (Equation 1), which maximizes the probability of producing the correct answer, and explicit in the difficulty estimation procedure (Section 3.2), which bins questions by pass@1 rate over 2048 samples. For problems where the base model's pass@1 is essentially zero, no test-time strategy can improve performance because there are no correct solutions to find or refine.

The consequence. Across all methods studied—search, revisions, and their compute-optimal combinations—the hardest difficulty bin (bin 5) shows near-zero improvement regardless of budget or strategy. The evidence is consistent across every experiment:

Figure 3 (right): On bin 5, both beam search and best-of-N weighted achieve ~1–3% accuracy at all budgets (4 to 256 generations). No scaling behavior is visible.
Figure 7 (right): On bin 5, all sequential-to-parallel ratios produce ~2–3% accuracy at 128 generations. The curve is flat.
Figure 9: The bin 5 scaling line is essentially flat near 0–5% for both revisions and PRM search, falling below the 14× larger model's performance at all R values.

This establishes a hard boundary: test-time compute amplifies existing capability but does not create it from nothing. For problems genuinely outside the base model's training distribution or reasoning capacity, no amount of test-time scaling helps. The practical implication is stark—for any deployment where a substantial fraction of queries are "hard" (the model rarely produces correct answers even with many attempts), compute-optimal test-time scaling offers essentially zero benefit over the base model's raw performance. The paper is candid about this (Section 7 takeaway box, Section 8), but the framing throughout (e.g., "simulate token-free behavior from a tokenized language model") can create an impression of broader capability than what the bin-5 results show.

What evidence exists in the paper. The bin-5 results appear consistently across Figures 3, 7, and 9. The paper does not analyze what makes bin-5 problems hard (e.g., whether they require knowledge the base model lacks, novel problem structures, or simply longer reasoning chains), nor does it attempt to stratify bin 5 further to see if some hard problems are more amenable to test-time compute than others. The 500-question test set, split into quintiles of ~100 each, means bin 5 contains ~100 questions—a meaningfully sized subset, but too small for fine-grained sub-analysis.

Mitigation status. Not addressed—and fundamentally, this limitation is inherent to the paradigm of test-time compute optimization and cannot be "fixed" without improving the base model. The paper acknowledges the boundary (Section 8 mentions that on hardest problems, "the base model simply lacks the capability" and "pretraining remains the only viable path"), but does not provide practitioners with tools to diagnose whether a given problem falls into this regime before spending the test-time budget. The difficulty estimator (Section 3.2) can identify bin-5 problems by their low pass@1, but only after paying the 2048-sample estimation cost. For a practitioner, the key operational question—"should I spend test-time compute on this query or escalate to a larger model / human?"—is answered only after the expensive difficulty estimation is complete. The paper does not explore cheaper methods for early detection of "no-hope" problems.

7. Implications and Future Directions

How This Work Changes the Landscape

This paper shifts how the field should think about tokenization: from a data preprocessing step whose effects are empirically measured and heuristically mitigated to a formal probabilistic transformation whose structural biases are mathematically characterized and algorithmically invertible. This is a reframing rather than a paradigm shift—tokenized LMs remain dominant, and the correction algorithms are presented as an inference-time add-on rather than a replacement for existing architectures—but the reframing has substantial conceptual and practical consequences.

Before this work, the standard narrative around tokenization was approximately: "Tokenization compresses text, enabling longer effective contexts for transformers, but introduces artifacts like spelling sensitivity, arithmetic failures, and cross-lingual unfairness. We don't fully understand why these artifacts occur, and the remedies are either to design better tokenizers, fine-tune with new vocabularies, or abandon tokenization entirely for token-free architectures." This narrative treated tokenization's effects as emergent empirical phenomena—things you discover by training models and measuring performance, with no a priori way to predict which inputs will cause problems.

The paper replaces this with a precise mechanistic account. The concepts of invalid encodings (Definition 2.2) and V* (the set of tokens that cannot appear as substrings of other tokens) together provide a predictive diagnostic: given only a vocabulary and encoding algorithm, one can identify exactly which conditioning events will produce sampling bias (when the last token of the encoding is not in V*) and which will not (when it is). This transforms tokenization analysis from post-hoc empirical debugging into formal verification. A practitioner examining a new tokenizer can compute V*, identify the bias-prone contexts, and quantify the structural distortion before training or deploying a single model.

The reconciliation of conflicting prior findings is implicit but important. The literature contained contradictory signals about tokenization's severity—some work found compression beneficial (Gallé, 2019; Gutierrez-Vasques et al., 2023), others identified counterexamples and failures (Cognetta et al., 2024; Schmidt et al., 2024; Xue et al., 2022). The paper's framework explains this contradiction: the presence and magnitude of bias depends on whether the specific conditioning contexts being evaluated end in V* tokens or not. Studies sampling different input distributions (different languages, domains, or prompt structures) would encounter different fractions of V*-stable versus V*-unstable contexts, producing apparently contradictory conclusions about tokenization's impact. This reconciles the conflict not by declaring one side right and the other wrong, but by identifying the structural variable (V* membership of the last conditioning token) that determines whether bias occurs. Future empirical studies on tokenization effects should control for this variable rather than reporting aggregate metrics that confound biased and unbiased cases.

The paper also redirects research attention in several specific ways:

Token-free modeling becomes less urgent as a standalone paradigm, but more relevant as a theoretical target. If tokenized LMs implicitly learn token-free distributions—as the theoretical framework and Markov chain experiments suggest—then demonstrating that a token-free architecture outperforms a tokenized one requires showing that the tokenized model fails to learn the character-level distribution, not merely that its standard interface fails to express it. The burden of proof shifts: token-free advocates must show that their models capture information that tokenized models fundamentally cannot represent, not just that tokenized models' naïve outputs are biased. At the same time, the paper's methods provide a way to measure token-free performance from tokenized models—by applying the correction algorithms and computing character-level perplexity—which creates a common evaluation ground that previously didn't exist. This could accelerate token-free research by providing a clearer target and a fairer comparison methodology.

Vocabulary design becomes more mathematically tractable. The V* criterion provides a concrete optimization objective for vocabulary construction: maximize the fraction of tokens in V* (to reduce bias-prone contexts) while maintaining compression efficiency. Prior work on vocabulary design optimized for compression rate or downstream task performance through empirical search. The paper's framework suggests that vocabulary size and composition can be analyzed for their bias properties before training, potentially enabling principled vocabulary construction that balances compression against bias. The observation that start tokens are typically in V* (Section 3.1, footnote) points to a design principle that could be extended: ensuring that common conditioning contexts end at V* boundaries would eliminate bias for those queries without any algorithmic correction.

Model evaluation methodology requires revision. The practice of evaluating tokenized LMs by computing perplexity over token sequences—the standard approach in the field—conflates model quality with tokenization quality. Two models with identical character-level knowledge but different tokenizers will have different token-level perplexities because the tokenization artifically segments the probability space differently. The paper provides a path toward tokenization-independent evaluation: compute character-level perplexity using the correction algorithms, eliminating the tokenization confound and enabling fair comparison across models with different vocabularies. This is particularly relevant for multilingual models, where the same model using different language-specific tokenizers would previously produce incomparable perplexity scores. The paper's Appendix A explicitly flags this implication in its discussion of Cao & Rimell (2021) and Chirkova et al. (2023), whose stochastic-tokenization evaluation methods the paper argues are "suboptimal" because they query models on invalid encodings.

Perhaps most provocatively, the paper opens the possibility of vocabulary transfer without fine-tuning. If any tokenized LM implicitly learns the token-free distribution, and the correction algorithms can extract that distribution, then one can—in principle—project the extracted distribution onto any other vocabulary using the conversion algorithm in Appendix F (which shows how to compute token-level probabilities from character-level ones). This would mean a model trained with one tokenizer could be deployed with a different tokenizer, without any weight modification, by inserting the correction-projection pipeline at inference time. The paper does not demonstrate this experimentally, and the computational cost of the full pipeline (extract character distribution via BPC, then project onto target tokens via Appendix F aggregation) would be substantial. But the theoretical possibility is genuinely novel: prior work on vocabulary adaptation (Minixhofer et al., 2024; Chen et al., 2023) required fine-tuning the embedding layer and continued training, while this approach would be purely inference-time.

Follow-Up Research This Work Enables

Character-level perplexity evaluation of pretrained LMs to measure tokenization-free performance. The paper provides algorithms to compute P(x_{n+1}^N \mid x_n^1) from any tokenized LM, which means character-level perplexity can now be computed for models like Llama, GPT-4, or Gemini without modifying them. A natural follow-up study would evaluate a suite of popular pretrained models on standard benchmarks (WikiText-2, PG-19, C4) using character-level perplexity computed through the BPC algorithm (since modern LMs use BPE), comparing against token-level perplexity and against token-free baselines like MegaByte or ByT5. Key measurements: (1) the absolute character-level perplexity achieved by tokenized models (are they competitive with dedicated token-free architectures?); (2) the gap between naïve token-querying character perplexity and corrected character perplexity (how much does the bias actually matter in aggregate for natural language?); (3) whether the Truncate-Renormalization procedure produces measurable perplexity improvements on real data, validating Proposition G.1 empirically beyond the toy Markov setting. A negative result—showing that the correction makes negligible difference on natural language benchmarks—would be equally informative, suggesting that the bias, while theoretically present, is practically small for typical NLP evaluation distributions.

Scaling the BPC algorithm to production vocabularies and measuring wall-clock cost. The paper's BPC algorithm (Appendix H) is proven correct for any BPE vocabulary, but its computational cost—O(n · M) LM calls for a string of length n with maximum token length M—is analyzed only theoretically. For a vocabulary of 32K tokens (Llama 2) or 100K tokens (GPT-4), and a continuation query of even 20 characters, the number of LM forward passes could be substantial. A critical engineering follow-up would implement BPC efficiently for a realistic vocabulary, profile the wall-clock time and memory usage on GPU hardware, and identify optimizations: precomputing the V^* set, caching LM outputs for repeated token histories, exploiting pretokenization boundaries (whitespace in BPE-based tokenizers) to reduce the search space by treating each whitespace-delimited segment as an independent unit, and using the refactoring step (Equation 1) to minimize query string length. The study should report concrete numbers: how many milliseconds per character, how this scales with vocabulary size, and whether the overhead is acceptable for interactive applications (latency < 100ms) or only suitable for offline batch evaluation. A negative finding—that the BPC cost is prohibitive for real-time use—would motivate research into approximate correction methods or hybrid strategies that apply full correction only for high-stakes queries.

Training difficulty prediction models to eliminate the 2048-sample estimation cost. The paper's difficulty estimation bottleneck—generating 2048 samples per question and averaging PRM scores—is the single largest barrier to practical deployment. A direct follow-up would train a lightweight classifier to predict difficulty bins from question text alone, using the 2048-sample PRM scores as training labels. The experiment: use the MATH training set (12,000 questions from Lightman et al., 2022), compute the PRM-based difficulty label for each question, train a small model (e.g., a fine-tuned BERT-base or a linear probe on PaLM 2-S*'s last hidden state) to predict the difficulty quintile from the question text alone, and evaluate on the 500-question test set. Key metrics: accuracy of bin prediction (chance is 20%), weighted accuracy (penalizing large bin misclassifications more than adjacent-bin errors), and—most importantly—the end-to-end performance of compute-optimal scaling when using the predicted difficulty versus the full PRM-based difficulty. If the predicted-difficulty scaling curve tracks the oracle curve as closely as the PRM-based curve does in Figure 4, the estimation cost drops from 2048 model calls to 1 (the prediction model) plus the strategy execution cost, making the approach deployment-ready. If prediction accuracy is poor, the exploration-exploitation tradeoff remains unresolved.

Combining the MPC/BPC correction with test-time compute scaling for tokenization-robust evaluation of reasoning. This paper studies tokenization bias correction; the prior example paper studied compute-optimal test-time scaling for math reasoning. A natural synthesis would investigate whether the test-time compute strategies' gains are partly due to overcoming tokenization bias (by generating multiple tokenizations that collectively cover more of the character-level probability space) or are orthogonal. The experiment: take a model trained on MATH with a BPE tokenizer, compute the correction for a subset of questions using the BPC algorithm to obtain character-level probability estimates of correct answers, and compare against the standard token-level probability estimates used in best-of-N scoring. If the character-level estimates assign higher probability to correct answers than the token-level estimates—especially for questions where the answer's tokenization is "unstable" (the last token is not in V*)—this would demonstrate that part of test-time compute's benefit comes from implicit tokenization debiasing through multiple samples. The follow-up would then combine explicit debiasing (BPC) with compute-optimal strategy selection, potentially achieving the 4× efficiency gain from the prior paper plus additional gains from removing residual bias.

Stress-testing the correction on adversarial tokenization scenarios. The paper's Markov chain experiments use randomly constructed transition matrices and hand-crafted vocabularies. A more systematic stress test would construct vocabularies specifically designed to maximize tokenization bias—for example, vocabularies where V* is very small (few "stable" tokens), or where common characters appear almost exclusively as substrings of longer tokens, or where the encoding of typical prompts systematically ends in non-V* tokens. The experiment would measure whether the correction algorithms maintain accuracy as bias severity increases, whether numerical precision degrades (due to multiplying many small probabilities in the recursive Pass steps), and whether the TR procedure remains effective when the fraction of probability mass assigned to invalid encodings by the base model is high. This would establish the operating envelope of the correction methods and identify failure modes that aren't visible in the paper's single vocabulary setting.

Empirical measurement of tokenization bias in deployed LMs across languages and domains. The paper provides the theory to predict when bias occurs (conditioning on non-V* tokens) but does not measure how large the bias is in practice or how it correlates with observable variables. A comprehensive empirical study would: (1) compute V* for vocabularies of major deployed models (Llama 2, Llama 3, GPT-4's reported vocabulary, Gemma, Mistral); (2) characterize what fraction of naturally occurring conditioning contexts in standard benchmarks (MMLU, HumanEval, GSM8K, multilingual benchmarks) end in V* versus non-V* tokens; (3) measure the bias magnitude by comparing corrected character-level probabilities against token-level probabilities for a sample of queries, reporting the distribution of divergence across queries; (4) break down results by language, since tokenization bias has been hypothesized to contribute to cross-lingual unfairness (Petrov et al., 2024)—languages with morphological structures that interact poorly with BPE merge priorities should show larger bias. This study would answer the practical question practitioners care about: "How worried should I be about tokenization bias for my specific use case?" without requiring them to implement the full correction pipeline.

Practical Applications and Downstream Use Cases

Character-level controllable text generation with tokenized LMs. When generating text with constraints at the character level—for example, ensuring output matches a specific regex pattern, generating valid code with exact syntax, or producing formatted data like JSON where character-level correctness is essential—the standard approach is to generate token-by-token and hope the decoded characters happen to satisfy the constraint. Tokenization bias means the model's token-level probabilities may be distorted in ways that make constrained generation unreliable even when the model "knows" the correct character-level distribution. Applying the correction algorithms during constrained decoding would provide the model's unbiased character-level probability estimates, which can then be filtered by the constraint. For instance, a code generation system that needs to produce exactly a specific variable name (a character-level constraint) could use MPC/BPC to compute P(next_character = 'x' | context) for each position, enforcing the constraint at the character level while still using the efficiently trained tokenized LM. The cost is the linear-per-character computational overhead of the correction, which for short constrained regions (a few tokens' worth of characters) is modest—perhaps 5–20 additional LM calls per constrained span.

Fairness auditing and debiasing of tokenized LMs across languages. Petrov et al. (2024) showed that tokenization introduces unfairness between languages because the same semantic content tokenizes differently, causing models to assign different probabilities to equivalent expressions. The correction algorithms provide a tokenization-neutral evaluation framework: by computing character-level probabilities using MPC/BPC, one can compare model behavior across languages with tokenization effects removed. A fairness audit would take a multilingual model (e.g., Llama 2 or Aya), construct parallel prompts in multiple languages that ask semantically equivalent questions, compute the corrected character-level probability of the correct answer in each language, and measure whether the gap between languages shrinks compared to standard token-level probability evaluation. If the gap persists after correction, the unfairness is in the model's semantic knowledge, not its tokenization; if it shrinks substantially, tokenization bias is the primary driver and the correction provides a partial remedy. This is actionable today for model developers deciding whether to invest in better multilingual tokenizers (vocabulary design) versus better multilingual pretraining data (knowledge acquisition).

Inter-model vocabulary transfer for efficient deployment. A scenario: an organization has fine-tuned a Llama-2-based model for a specialized domain but wants to deploy it using a smaller, faster vocabulary (e.g., a domain-specific BPE vocabulary with fewer tokens) to reduce inference latency. Currently, this requires either retraining the entire model with the new vocabulary (expensive) or using heuristic embedding initialization and continued training (Minixhofer et al., 2024; still requires training). The paper's framework suggests a training-free alternative: use the BPC algorithm to extract character-level distributions from the original model, then use the Appendix F aggregation algorithm to project these distributions onto the target vocabulary, effectively simulating the target-vocabulary model at inference time. The computational cost is high—each token prediction in the target vocabulary requires multiple character-level queries to the original model—but for applications where inference is cheap relative to training (e.g., batch processing where latency is not critical, or where the original model must be preserved unchanged for compliance reasons), this could be the only viable option. A practical implementation would cache frequently queried character-level probabilities and exploit the fact that many tokens share prefixes to amortize the correction cost.

Character-level scoring for educational applications. In educational settings where an LM evaluates student answers, tokenization bias can cause unfair scoring: a student whose answer tokenizes "unfavorably" (ending with a non-V* token that restricts the model's probability space) might receive a lower score than a student with a semantically equivalent answer that tokenizes "favorably." The correction algorithms enable tokenization-invariant scoring: compute the corrected character-level probability of each student's answer given the question, producing scores that depend only on the character content, not on how the tokenizer happened to segment it. This is particularly relevant for evaluating short answers (a few words to a sentence) where the tokenization of the answer boundary can significantly affect the LM's probability estimate. The linear-per-character cost of MPC/BPC is acceptable for scoring applications where each answer is evaluated once, offline, rather than in an interactive setting.

When to Prefer This Method

The paper positions its correction algorithms as a general-purpose inference-time debiasing method for any tokenized LM, without articulating specific tradeoffs against named alternatives for the same problem. The natural alternatives—token-free models or vocabulary adaptation—operate at different stages of the pipeline (architecture design or training, respectively), so the choice is not "use correction instead of X" but rather "given that I already have a tokenized LM, should I apply correction?" The paper does not provide the empirical comparisons (to token-free models, to heuristic boundary-correction methods like guidance.ai) that would enable a decision matrix. As such, the following conditions emerge from the paper's theoretical framework and experiments, with the caveat that no head-to-head experimental comparison exists:

Prefer applying the MPC/BPC correction when: (1) You have a pretrained tokenized LM that cannot be retrained or fine-tuned (deployment constraint), and you need character-level probability estimates for tasks where tokenization bias is likely severe—specifically, when your conditioning contexts frequently end with tokens not in V* (diagnosable from the vocabulary alone). The Markov chain experiments show that bias can be extreme (probability 1.0 vs. ground truth α) in such contexts, so correction is essential for any application requiring accurate character-level probabilities. (2) You are evaluating or comparing models with different tokenizers and need a tokenization-independent metric (character-level perplexity). The correction algorithms provide the only known method to compute this metric from tokenized models without retraining. (3) The computational budget for inference is sufficient to accommodate the linear-per-character overhead of MPC or the higher cost of BPC—this is likely true for offline evaluation and batch processing, but may not hold for real-time interactive applications with strict latency requirements.
Prefer token-free models directly when: Training a new model from scratch is feasible, and the primary application demands character-level reasoning pervasively (e.g., character-level machine translation, byte-level file generation). In this regime, the ongoing inference-time overhead of correction across every query would accumulate to exceed the one-time cost of training a token-free architecture, and the token-free model avoids the correction complexity entirely. The paper acknowledges that token-free models currently underperform tokenized ones (Yu et al., 2024), so this preference assumes future token-free models close the performance gap or that the specific application does not require state-of-the-art quality.
Prefer vocabulary adaptation (fine-tuning) when: You can modify model weights and have access to continued training resources, and the target vocabulary is substantially better for your domain than the original vocabulary (e.g., adapting a general-purpose model to a specialized domain with very different token frequency distributions). Vocabulary adaptation changes the model's internal representations to align with the new tokenization, potentially achieving better efficiency than inference-time correction because the model's computation is restructured around the target vocabulary rather than simulating it through the original vocabulary. However, the paper's theoretical framework implies that vocabulary adaptation does not eliminate bias—it merely shifts which contexts are biased—so correction algorithms would still be needed even after adaptation if character-level accuracy is required. The two approaches are complementary rather than exclusive.