REVIEW 3 major objections 5 minor 1 cited by
Language Models over Canonical Byte-Pair Encodings
T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read Restricting a token-level language model to canonical BPE strings provably lowers its KL divergence and improves held-out log-loss, with a simple bigram test making the constraint practical.
desk verdict The bigram canonicality test and the local conditioning scheme are genuinely useful, but the headline likelihood gains are mostly a renormalization artifact, and the hand-fitted pre-tokenizer overrides leave the formal guarantees one step removed from the experiments. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the canonicalization function $\varphi(\delta) = \tau(\kappa(\delta))$, which re-encodes a token string by decoding it to characters and running the BPE encoder again, together with the set $D$ of canonical token strings. The main identity is Theorem 1, $D = B$: a token string is canonical exactly when all adjacent token pairs are canonical, so canonicality can be checked by a bigram test rather than by running the full BPE encoder. This identity feeds the local model's next-token masking rule, the estimate of the canonicality rate $Z$ via importance sampling with weights $w_\ell(\delta) = p_\Delta(\delta)/(\ell(\delta) \mathbf{1}\{\delta \in D\})$, and the proofs that conditioning lowers KL divergence.
What would settle it
Run the paper's bigram test on all token bigrams in a large corpus of canonical strings for GPT-2 and Llama and compare against the round-trip check $\varphi(\delta)=\delta$; any bigram the test rejects but the round-trip check accepts is a false negative. If one appears outside the paper's override set, the local model assigns zero probability to the corresponding canonical strings, so the claimed KL guarantee of Proposition 3 fails for those strings.
Extended reading notes
Core claim
The paper's central discovery is that the canonicality constraint, the requirement that a token-level language model assign positive probability only to token strings realizable by the deterministic BPE tokenizer, is cheap to enforce and strictly beneficial. Assuming the true token distribution is canonical, the globally canonicalized model $g$, defined as the base model conditioned on membership in the canonical set $D$, satisfies $KL(p^\star_\Delta \| p_\Delta) - KL(p^\star_\Delta \| g) = -\log Z \geq 0$, so it can only improve fit; the locally canonicalized model $\ell$, which masks only the next tokens that would make the prefix noncanonical, satisfies an analogous inequality through its warping weights. The paper proves Theorem 1: a BPE token string is canonical if and only if every token bigram in it is canonical, which makes the constraint practical to test incrementally. Empirically, enforcing canonicality reduces held-out log-loss on PTB and WikiText for GPT-2 small, medium, and large, and for Llama 3.2-1B, 3.2-3B, and 3.1-8B, and fine-tuning an architecture that builds the constraint into its output layer yields a further small gain.
Load-bearing premise
The practical methods depend on the bigram canonicality test matching the real tokenizer exactly, but because production GPT-2 and Llama tokenizers add a pre-tokenization step, the test can wrongly reject some canonical strings, and the paper fixes only the mistakes it found with a manually determined override set.
Editorial extensions
If this is right
- Any BPE-tokenized language model that puts mass on noncanonical strings can be strictly improved in KL divergence at test time by renormalizing over canonical strings, with the improvement exactly $\log(1/Z)$.
- The bigram test makes canonicality constraints practical for generation: the locally canonicalized model can be sampled at nearly the same cost as the base model, only masking next tokens that break canonicality.
- Canonicality can be baked into an architecture, and fine-tuning the constrained model with a KL regularizer gives held-out log-loss improvements over fine-tuning the unconstrained model.
- Because $D = \overrightarrow{D}$ for BPE, a string is a canonical prefix if and only if it is canonical, so decoding can be checked incrementally during autoregressive generation.
- The improvement in log-loss is statistically significant for every string and every tested model, since the correction is positive per string and constant for the global method.
Reading between the lines
- The same conditioning argument should transfer to other deterministic tokenizers with efficient membership tests, such as longest-match or WordPiece-style tokenizers, though the identity $D = \overrightarrow{D}$ does not hold there, so prefix checks would need separate treatment.
- Because the paper measures only task-agnostic likelihood, whether canonicality helps or hurts on downstream task metrics remains untested; the paper explicitly leaves that as an open direction.
- A complete fix for the pre-tokenizer interaction would build a finite-state transducer modeling the pre-tokenizer and compose it with BPE, replacing the hand-fitted override set.
- One could distill the globally canonicalized model $g$ into a canonical architecture by minimizing $KL(g\|\ell_\theta)$, a route the paper mentions as future work, giving fast approximate-canonical sampling without the local model's warping.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper formalizes byte-pair encoding (BPE) as a deterministic tokenization model (Σ, Δ, τ, κ) and defines the set D of canonical token strings, i.e., strings of the form τ(σ). It observes that a token-level language model pΔ assigns positive probability to noncanonical token strings and proposes two families of methods to enforce canonicality: (i) canonicality by conditioning, which includes a globally canonicalized model g obtained by conditioning pΔ on D, and a locally canonicalized model ℓ defined autoregressively by masking out non-canonical extensions; and (ii) canonicality by construction, a parameterized architecture ℓθ that enforces the constraint during fine-tuning. The paper proves several theoretical results: Propositions 1 and 3 show that g and ℓ reduce KL divergence to the true (canonical) token distribution; Proposition 4 gives an importance-sampling estimator of the canonicality rate Z; and Theorem 1 shows that for BPE a token string is canonical iff every adjacent bigram is canonical, leading to an efficient incremental membership test. Experiments on GPT-2 and Llama models over PTB and WikiText report lower held-out log-loss for the canonicalized models relative to the baseline pΔ.
Significance. The formal framework is clean and the central structural result (Theorem 1, D = B) is an elegant and useful characterization of BPE canonicality; it is simpler than prior automaton-based tests. The proof of Proposition 1 is a correct, parameter-free derivation, and Proposition 3 provides a genuine guarantee for the local method once the missing pointwise inequality is supplied. The paper ships code and is honest about the limitations of its empirical work, including the small gains from fine-tuning and the absence of downstream-task evaluations. If the practical canonicality test can be made exact for real pre-tokenizer-equipped tokenizers, the methods are directly applicable to a broad class of BPE-based models. The main value of the paper is therefore the combination of a simple theoretical observation with a practical, efficient test, rather than the magnitude of the reported log-loss improvements, which are partly definitional for the global method.
major comments (3)
- [App. B.2 (Assumption 1) and Theorem 1] Assumption 1 ('For all δ ∈ ∆, φ(δ) = δ') is load-bearing for Theorem 1, Lemma 3, and Proposition 5, since the base cases P(0) and P(1) in the proof of Theorem 1 require every single-token string to be canonical. The manuscript states this assumption 'for simplicity' but never reports checking it for the GPT-2 and Llama tokenizers used in §5. If any vocabulary token fails the assumption, the bigram test returns wrong answers for bigrams containing that token, and the override set in §5.1 was constructed only for pre-tokenizer-induced false negatives, not for single-token noncanonicality. Please verify Assumption 1 on the actual vocabularies and report the number of violations (if any), or extend the test and theory to handle noncanonical tokens.
- [§5.1, Footnote 12, and App. A (Precision vs. recall)] The incremental bigram test 'occasionally makes some mistakes' because of pre-tokenizer interaction, and the fix is a hand-determined override set discovered on a corpus of canonical strings. As the paper itself notes in Footnote 12, false negatives break the support condition pΔ(δ)1{δ ∈ D} > 0 =⇒ ℓ(δ) > 0 required for Proposition 3, and they also bias the importance-sampling estimator Ẑ in Eq. (13) and hence the reported global improvement L(g) = L(pΔ) + log Ẑ in Eq. (18b). Since the override set is derived from a finite corpus, canonical bigrams outside that corpus are unprotected, and App. A ('Precision vs. recall') concedes that 'it may be impossible to capture every nuance of a particular implementation perfectly.' The paper should either implement the exact pre-tokenizer-aware transducer composition mentioned in Footnote 15, or provide a quantitative bound on the residual false-negative rate on a held-out corpus together with an analysis of its worst-case effect on the log-loss numbers in Fig. 3.
- [App. D, proof of Proposition 3] The proof of Proposition 3 derives KL(p*Δ ∥ ℓ) = KL(p*Δ ∥ pΔ) + E_{δ∼p*Δ}[log wℓ(δ)] and then asserts that the reduction −E[log wℓ(δ)] is ≥ 0. This nonnegativity does not follow from the displayed algebra; it requires the pointwise bound wℓ(δ) ≤ 1 for all δ ∈ D, which holds because each normalization factor −→ℓ(δ<t) in Eq. (10a) is a probability of a set of continuations and hence at most 1. Please state and prove this bound explicitly, since it is the step that guarantees the local canonicalization cannot increase KL divergence.
minor comments (5)
- [Definition 2 (Eq. 9a–9d)] The symbol ℓ is overloaded: ℓ(δ) denotes both the probability of the token string δ (Eq. 9a) and the normalization factor for the prefix extension distribution (Eq. 9d uses −→ℓ, but the arrow is dropped in several sentences, e.g., '−→ℓ(δ) normalizes the distribution'). Please rename the normalization factor (e.g., N(δ)) to avoid confusion.
- [§5.2, Statistical significance] The statements that the global and local improvements are 'trivially statistically significantly better' with p = 0 are correct only because the per-string log-loss difference is nonnegative for every single held-out string; this is a definitional property rather than a sampling-based inference. The text should say so explicitly rather than invoking a paired-permutation test as if it involved sampling variability.
- [Abstract and §1] The claim that noncanonical token strings 'will never be seen in any training corpus, no matter how large' is true for the idealized exact tokenizer, but the paper later shows in §5.1 that the real GPT-2 and Llama tokenizers, with their pre-tokenization steps, can require case-dependent canonicality judgments. Please qualify the abstract's statement to avoid overgeneralization.
- [Fig. 3 and §5.2] Fig. 3 reports log-loss values without confidence intervals, while Fig. 4 provides confidence intervals for log Ẑ. Since the local method's improvement is dataset-dependent and the global improvement is a deterministic function of Ẑ, please report standard errors for the local log-loss estimates or otherwise quantify the variability of the per-string weights.
- [§5.2 heading] The heading 'Methology' should be corrected to 'Methodology'.
Circularity Check
The reported likelihood gains of the global and local conditioning methods are the defining renormalization constants (Eq. 18b/18c), so the headline improvement reduces by construction; the bigram-test and fine-tuning contributions remain independent.
-
self definitional
[§3.1 Definition 1 (Eq. 6d–6e), Proposition 1 (Eq. 7); §5.2 Eq. (18b)]
"g(δ) = 1/Z p∆(δ)1{δ ∈ D} ... where Z is the canonicality rate: Z = Pr_{Y∼p∆}[Y ∈ D] ... L(g) = L(p∆) + log Z ≈ L(p∆) + log bZ ... Note that log bZ ≤ 0; thus, the global method can only improve the log-loss, L(g) ≤ L(p∆)."
The global method is defined as renormalizing p∆ over the canonical set D (Def. 1), and held-out strings are canonical by construction. Its reported log-loss is therefore computed as L(p∆)+log bZ (Eq. 18b), so the 'improvement' is exactly the estimated normalizer Z. Since Z is a probability, log Z ≤ 0, making the improvement a logical consequence of the definition rather than an independently measured or predicted outcome. Proposition 1's KL reduction is the same identity: KL(p⋆∆∥g) = KL(p⋆∆∥p∆)+log Z. The theorem is valid, but it restates the defining renormalization.
-
self definitional
[§3.2.2 Definition 2, Proposition 2 (Eq. 10a); §5.2 Eq. (18c)]
"ℓ(δ) = p∆(δ) 1{δ ∈ D} [∏_{t=1}^{|δ|+1} −→ℓ(δ<t)]^{−1} ... L(ℓ) = L(p∆) + 1/M Σ_{m=1}^M log wℓ(δ^{(m)}) ... Note that 1/M Σ log wℓ(δ^{(m)}) ≤ 0; thus, the local method can only improve the log-loss, L(ℓ) ≤ L(p∆)."
The local model ℓ is built by renormalizing each next-token conditional of p∆ to the set of prefix-canonical extensions (Def. 2). Its weight wℓ(δ) is the product of these per-step normalizers, and each normalizer is ≤ 1 because it is a sum over a subset of the conditional distribution. Hence the reported log-loss gain is the sample mean of log wℓ on held-out canonical strings, non-positive by construction. The improvement in Prop. 3 is the same identity in expectation, so it too is the defining renormalization rather than a fitted or independently verified prediction.
full rationale
The paper's two conditioning results are valid identities, but the headline 'improvement' is built into the renormalization: L(g) = L(p∆)+log Z and L(ℓ) = L(p∆)+E log wℓ, with log Z ≤ 0 and log wℓ ≤ 0 by definition. Because the evaluation is restricted to canonical strings, the improvement is not an empirical discovery about the models; it is the normalizer. The paper is transparent about this ('trivially statistically significantly better ... p = 0'), which lowers the severity. The independent contributions are the efficient incremental bigram test (Theorem 1, Prop. 5), the fine-tuning experiments with the canonicalized architecture (§5.3), and the honest treatment of the pre-tokenizer approximation. The pre-tokenizer issue (§5.1, Footnote 12, App. A 'Precision vs. recall') is a genuine correctness limitation: false negatives can break Prop. 3 and bias bZ downward, as the paper itself concedes, but this is an engineering/exactness gap, not a circular step. Self-citations (Gastaldi et al. 2025, Vieira et al. 2024, Amini et al. 2025) are used for definitions and estimators, not as load-bearing uniqueness arguments. Overall, the central theoretical claims reduce by construction, giving partial circularity (6), while the practical algorithm and fine-tuning results retain independent content.
Assumptions & free parameters
free parameters (3)
- canonicality test overrides =
unspecified set of bigrams
- regularization parameter lambda =
0.001, 0.01, 0.1, 0.2 (grid)
- maximum string length for GPT-2 =
1024
assumptions (4)
- standard math Exact tokenization model: κ(τ(σ))=σ for all strings σ.
- domain assumption Assumption 1: every token in the vocabulary is canonical, i.e., φ(δ)=δ for all δ∈∆.
- domain assumption The true token-level distribution p⋆Δ has support only on canonical strings D.
- ad hoc to paper The pre-tokenizer interacts with BPE in a way that is fully captured by the override set (i.e., no false negatives outside the override set).
Cite this review
Pith. "Pith review of Language Models over Canonical Byte-Pair Encodings." pith.science (2026). https://pith.science/paper/LJEO4HHJ
@misc{pith2026250607956,
author = {Pith},
title = {Pith review of: Language Models over Canonical Byte-Pair Encodings},
year = {2026},
howpublished = {\url{https://pith.science/paper/LJEO4HHJ}},
note = {Machine review of arXiv:2506.07956}
}
abstract
Modern language models represent probability distributions over character strings as distributions over (shorter) token strings derived via a deterministic tokenizer, such as byte-pair encoding. While this approach is highly effective at scaling up language models to large corpora, its current incarnations have a concerning property: the model assigns nonzero probability mass to an exponential number of $\it{noncanonical}$ token encodings of each character string -- these are token strings that decode to valid character strings but are impossible under the deterministic tokenizer (i.e., they will never be seen in any training corpus, no matter how large). This misallocation is both erroneous, as noncanonical strings never appear in training data, and wasteful, diverting probability mass away from plausible outputs. These are avoidable mistakes! In this work, we propose methods to enforce canonicality in token-level language models, ensuring that only canonical token strings are assigned positive probability. We present two approaches: (1) canonicality by conditioning, leveraging test-time inference strategies without additional training, and (2) canonicality by construction, a model parameterization that guarantees canonical outputs but requires training. We demonstrate that fixing canonicality mistakes improves the likelihood of held-out data for several models and corpora.
Figures
Figures from the paper (1 more)
Forward citations
Cited by 1 Pith paper
-
Language Models are not Equally Robust to Non-Canonical Tokenization across Languages
Tokenization invariance does not generalize beyond English: non-canonical segmentations cut multilingual LLM task scores by ~10–24% on average, worse for high-fragmentation languages, and multi-tokenization LoRA mitig...
Reference graph
Works this paper leans on
-
[1]
Suppose t < T, then the (t+1)th step of φ(abc) applies to the highest-priority23 bigram of a(t)b(t)c(t). Consider the following subcases characterizing the possible positions for this merge: (a) The merge is in a(t). Then, (at+1, bt+1, ct+1, dt+1, et+1) = (at + 1, bt, ct, dt + 1, et) satisfies Pt+1 because • It must also be the highest-priority merge in a...
-
[2]
Suppose t ≥ T . No merges exist. Then, (at+1, bt+1, ct+1, dt+1, et+1) = (at, bt, ct, dt, et) satisfies Pt+1 because φt(abc) = φT (abc) = a(t)b(t)c(t) = a(T )b(T )c(T ), by definition of T , which implies that no further changes are possible and all processes must copy their position on this step, and continue to do so forever. Therefore, Pt holds for all ...
-
[3]
=⇒ by Theorem 1, the bigrams of δ′ are all canonical
-
[4]
=⇒ since δ ⪯ δ′, its bigrams are a subset of those of δ′, so they are also all canonical
-
[5]
=⇒ since the bigrams of δ are all canonical, by Theorem 1, δ ∈ D Therefore, − →D = D. ■ 26More generally, Lemma 3 holds for any tokenization model with a bigram-based canonicality test (i.e., δ ∈ D ⇐ ⇒BIGRAMS (δ) ⊆ B. 21 Language Models over Canonical Byte-Pair Encodings B.3. An Even Faster Bigram Test BPE derivations. Our canonicality test involves the i...
-
[6]
=⇒ by definition of − →D , there is a δ′ ∈ Dsuch that δ ⪯ δ′
- [7]
-
[10]
Suppose ¬Φ(δ, δ′). Then, there exists a conflicting pair ⟨s, s′⟩ = find_conflict(δ, δ′), i.e., ⟨s, s′⟩ satisfies π(s) > ⟨s, s′⟩ ≤π(s′). Below is a schematic representation of such a conflict: γ(δ) µ1 π(s) µℓ s ··· ··· γ(δ′) π(s′) s′ µ′ r µ′ 1 ··· ··· conflict > ⟨s, s′⟩ ≤
Show all 30 references
-
[11]
Thus, the conflicting merge ⟨s, s′⟩ would have been preferred by τ if it were run on the character string κ(δ·δ′): µ1 ··· µℓ ⟨s, s′⟩ s′s µ′ r ··· µ′ 1 the conflicting merge blocks both of the merges below because π(s) = ⟨µℓ, s⟩ > ⟨s, s′⟩ and π(s′) = ⟨s′, µ′ r⟩ ≥ ⟨s, s′⟩:30 µ1 ...
-
[12]
Part 2 (¬Φ(δ, δ′) ⇐= δ·δ′ /∈ B)
The existence of this intermediate step means that it is impossible for δ·δ′ to be a canonical bigram; thus, δ·δ′ /∈ B. Part 2 (¬Φ(δ, δ′) ⇐= δ·δ′ /∈ B)
-
[13]
Then, φ(δ·δ′) ̸= δ·δ′, by definition
Suppose δ·δ′ /∈ B. Then, φ(δ·δ′) ̸= δ·δ′, by definition
-
[14]
Then, there must exist a conflicting merge ⟨s, s′⟩ as a subtree in φ(δ·δ′) that blocks δ·δ′ from being built. Now, because both δ and δ′ are canonical in isolation (Assumption 1), the conflict⟨s, s′⟩ must straddle the boundary between theδ and δ′: s s′ γ(δ) ⟨s, s′⟩ γ(δ′) This ...
-
[15]
This characterization is equivalent to ¬Φ(δ, δ′). ■ 30Note that ⟨s, s′⟩ < π(s) enforces the left-most merge preference in BPE’s encoding procedure τ, i.e., in the event of a tie between overlapping merges of the same rank, the left-most merge is taken. 24 Language Models over ...
2024
-
[16]
=⇒ ∃σ ∈ Σ∗ : δ = τ (σ) by definition of D
-
[17]
=⇒ κ(τ (σ)) = σ by exactness assumption
-
[18]
=⇒ τ (κ(τ (σ))) = τ (σ) because τ is a function
-
[19]
=⇒ τ (κ(δ)) = δ substitute τ (σ) 7→ δ
-
[20]
=⇒ φ(δ) = δ by definition of φ
-
[22]
=⇒ ∃σ ∈ Σ∗ : δ = τ (σ); specifically, σ = τ (δ)
-
[23]
=⇒ δ ∈ Dby definition of D
-
[24]
Since each directions have been proven, the proposition holds
Thus, this direction holds. Since each directions have been proven, the proposition holds. ■ Corollary 1. D = {φ(δ) | δ ∈ ∆∗} (27) Proposition 7. Let (τ , κ) be exact. Then, (τ , κ) is a bijection between (Σ∗, D). Proof. The bijection follows directly from the following: • Exa...
-
[25]
=⇒ τ (κ(δ)) = δ′ by definition of φ
-
[26]
=⇒ τ (κ(τ (κ(δ)))) = τ (κ(δ′)) because τ and κ are functions
-
[27]
=⇒ τ ( κ( τ (κ(δ)))) = τ (κ(δ′)) by exactness
-
[28]
=⇒ τ (κ(δ)) = τ (κ(δ′))
-
[29]
=⇒ τ (κ(δ)) = τ (κ(φ(δ))) substitution δ′ 7→ φ(δ)
-
[30]
Proofs for Section 4 (Canonicality by Conditioning) Proposition 1
=⇒ φ(δ) = φ(φ(δ)) by definition of φ ■ 26 Language Models over Canonical Byte-Pair Encodings D. Proofs for Section 4 (Canonicality by Conditioning) Proposition 1. Assuming that the true distribution over tokens p⋆ ∆ is canonical, the globally canonicalized model g guarantees t...
2000
-
[1993]
"".encode(
URL https://aclanthology.org/J93-2004/. Merity, S., Xiong, C., Bradbury, J., and Socher, R. Pointer sentinel mixture models. In International Conference on Learning Representations , 2017. URL https:// openreview.net/forum?id=Byj72udxe. Mikolov, T., Karafiát, M., Burget, L., ˇ...
2024 arXiv
-
[2023]
Black, S., Biderman, S., Hallahan, E., Anthony, Q., Gao, L., Golding, L., He, H., Leahy, C., McDonell, K., Phang, J., Pieler, M., Prashanth, U
URL https://proceedings.mlr.press/v202/ biderman23a.html. Black, S., Biderman, S., Hallahan, E., Anthony, Q., Gao, L., Golding, L., He, H., Leahy, C., McDonell, K., Phang, J., Pieler, M., Prashanth, U. S., Purohit, S., Reynolds, L., Tow, J., Wang, B., and Weinbach, S. GPT-NeoX...
2022 arXiv
-
[2025]
Gemma Team
URL https://arxiv.org/abs/2407.11606. Gemma Team. Gemma: Open models based on Gemini research and technology, 2024. URL https://arxiv. org/abs/2403.08295. Groeneveld, D., Beltagy, I., Walsh, E., Bhagia, A., Kin- ney, R., Tafjord, O., Jha, A., Ivison, H., Magnusson, I., Wang, Y...
2024 arXiv
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.