{"id":"61430cb1-0ae7-43c5-9941-8513ce84647d","arxiv_id":"2506.07956","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Enforcing canonical BPE tokenizations through conditioning or architectural constraints improves held-out likelihood for GPT-2 and Llama models.","lead":"Language models built on byte-pair encoding assign probability to token sequences that the tokenizer can never produce. This paper shows how to renormalize or fine-tune them so only valid tokenizations receive probability, and that this improves likelihood on test data.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The load-bearing risk is the approximate bigram test: false negatives outside the override set would break Prop. 3 and bias the importance-sampling estimate of Z; an exact pre-tokenizer-aware oracle is needed to close the gap.","rationale":"Proposition 1 and Proposition 3 are correct under their stated idealization: conditioning on the canonical event or masking noncanonical extensions can only reduce KL to a canonical p*Δ, and the proofs in App. D check out. The nontrivial gap is between the formal BPE model in App. B and the real tokenizers with pre-tokenization used in §5. The paper is transparent about this gap, but the hand-fitted override set is an empirical patch, not a formal guarantee, so the central practical claim inherits the risk of remaining false negatives. This is the same weakest assumption the reader identified. An exact transducer-based oracle would settle it. The other reader concern—that the empirical gain is a mathematical consequence of renormalization rather than an independent validation—is fair but does not change the correctness of the claims; it mainly limits what the experiments add. Because the reader's CONDITIONAL verdict already captures the right level of confidence, I recommend no change.","tokens_in":33213,"tokens_out":16346,"duration_ms":197916,"concrete_test":"Implement the exact canonicality oracle that §5.1's footnote 15 defers: compose a finite-state transducer for each pre-tokenizer regex (GPT-2 and Llama) with the BPE merge transducer, producing the true prefix-canonical language -→D. Compare this oracle against the bigram test plus the override set on (a) all token bigrams, or a large random sample if exhaustive comparison is infeasible, and (b) every bigram appearing in the PTB and WikiText test sets. For every canonical test string δ, verify the support condition ℓ(δ)>0. Then recompute L(ℓ), L(g), and bZ using the oracle; if any reported log-loss improvement or local-vs-global ranking changes, the pre-tokenizer approximation is load-bearing and the experiments must be rerun with the exact test.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's practical methods rely on the incremental bigram test for -→D (Prop. 5 / App. B), but §5.1 concedes that with real pre-tokenizers the test \"occasionally makes some mistakes,\" and the workaround is a hand-fitted set of overrides discovered on a corpus of canonical strings. The theory, including Prop. 3 and the unbiasedness of bZ in Prop. 4, requires the test to be exact: Footnote 12 states that false negatives break the support condition p∆(δ)1{δ∈D}>0 ⟹ ℓ(δ)>0. If any canonical token string δ is assigned ℓ(δ)=0 by a missed false negative, then KL(p*Δ∥ℓ) becomes infinite, the claimed KL reduction in Prop. 3 no longer holds, and the importance-sampling estimator bZ of Z is biased downward, making the reported global log-loss improvement L(g)=L(p∆)+log bZ look larger than it truly is. Because the overrides are derived from a finite corpus, canonical bigrams outside that corpus are unprotected; App. A's \"Precision vs. recall\" paragraph acknowledges that capturing every nuance of a reference implementation may be impossible. This is the most load-bearing assumption connecting the formal results to the experiments.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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Δ.","tokens_in":33482,"tokens_out":11455,"duration_ms":122307,"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":[{"comment":"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.","section":"App. B.2 (Assumption 1) and Theorem 1"},{"comment":"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.","section":"§5.1, Footnote 12, and App. A (Precision vs. recall)"},{"comment":"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.","section":"App. D, proof of Proposition 3"}],"minor_comments":[{"comment":"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.","section":"Definition 2 (Eq. 9a–9d)"},{"comment":"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.","section":"§5.2, Statistical significance"},{"comment":"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.","section":"Abstract and §1"},{"comment":"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.","section":"Fig. 3 and §5.2"},{"comment":"The heading 'Methology' should be corrected to 'Methodology'.","section":"§5.2 heading"}],"recommendation":"major_revision","confidential_remarks":"The paper has a solid formal core but the empirical validation rests on an approximate, hand-patched canonicality test. The authors are well-known in the area and the citation practice seems appropriate. The novelty is moderate — the main theorems are straightforward once D = B is proven, and the bigram test is the most useful contribution. For this journal, the revision should focus on making the practical test exact (or rigorously bounding its errors) and on verifying Assumption 1; without that, the headline empirical claim is only as strong as the override set."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this paper is worth reading, and it deserves a real referee, but not for the headline number. The genuinely new things are the bigram characterization of BPE canonicality (D = B), the efficient incremental test, and the local conditioning scheme. Those are clean, implementable, and simpler than the automaton-heavy prior work. The theoretical claims (Props 1 and 3) are correct under their assumptions; the proofs are straightforward and the KL reductions are real.\n\nThe soft spots are exactly where you'd expect. The global method's improvement is L(g) = L(p∆) + log Z, so it is a renormalization of the canonical strings. Since the held-out strings are canonical by construction, the \"improvement\" is the normalization constant itself, not independent evidence about the model. The paper says as much in §3.1, but the experimental framing in Fig. 3 can leave the wrong impression. The local method is a reweighting, not a renormalization, and its gain is real but small.\n\nThe larger concern is the approximate bigram test. §5.1 concedes the test \"occasionally makes some mistakes\" with real pre-tokenizers, and the patch is a hand-fitted override set. Footnote 12 is explicit: false negatives break the support condition and bias the importance-sampling estimate of Z. Appendix A's \"Precision vs. recall\" paragraph admits capturing every nuance of a reference implementation may be impossible. So the formal guarantees hold for the ideal BPE-only tokenizer; for GPT-2 and Llama, correctness is an empirical property of the override set, not the theorem. That is a real gap, and the stress-test note is right to call it load-bearing. It is not fatal to the paper's value, but it should be a central item for any revision: give an exact pre-tokenizer-aware transducer, or bound the impact of residual false negatives.\n\nThe fine-tuning section is the thinnest part: two small models, no error bars, small gains. The authors flag it as a proof of concept, which is fair.\n\nWho is this for? People working on tokenization-aware decoding, finite-state views of BPE, or the probabilistic semantics of tokenizers. I'd cite the bigram test; I'd be cautious about citing the \"canonicality improves likelihood\" framing. My verdict: serious referee, major revision. The core math and the test deserve scrutiny; the empirical claims need to be de-emphasized or supported by an exact test.","headline":"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.","tokens_in":34057,"tokens_out":2734,"would_cite":true,"duration_ms":30077,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["byte-pair encoding","canonical token strings","token-level language models","KL divergence","canonicality by conditioning","canonicality by construction","bigram canonicality test","pre-tokenization"],"falsifier":"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.","tokens_in":32984,"feed_emoji":"🔤","tokens_out":7025,"duration_ms":77192,"temperature":0.7,"pith_summary":"Byte-pair encoding (BPE) is a deterministic scheme that replaces each character string with a single token string, yet token-level language models trained on BPE also spread probability over exponentially many noncanonical token strings that decode to valid text but could never be produced by the tokenizer. The paper claims this probability mass is wasted and can be removed without hurting the model: conditioning a token-level model on the set of canonical strings, or masking noncanonical next tokens during decoding, provably decreases KL divergence to the true token distribution, assuming that distribution is canonical. The paper gives two implementation strategies, one test-time and one architectural, plus an efficient incremental canonicality test that reduces checking whether a BPE string is canonical to checking each adjacent pair of tokens. On held-out data from Penn Treebank and WikiText, the constrained models achieve lower log-loss than their unconstrained baselines across GPT-2 and Llama models.","feed_headline":"Zero out impossible BPE encodings to cut LM log-loss","feed_subtitle":"Enforcing canonical token strings provably lowers KL divergence and cuts held-out log-loss on GPT-2 and Llama.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduces the byte-pair encoding data-compression algorithm that the paper formalizes as the tokenization scheme.","marker":"Gage, 1994"},{"why":"Brings BPE into neural machine translation as a subword tokenization method, the practice the paper analyzes.","marker":"Sennrich et al., 2016"},{"why":"Provides the exact tokenization-model formalism and consistency conditions that the paper's canonicality definitions build on.","marker":"Gastaldi et al., 2025"},{"why":"Constructs a BPE tokenization DFA; the paper's bigram test is presented as a simpler alternative that avoids automata theory.","marker":"Berglund et al., 2024"},{"why":"Treats tokenization as finite-state transduction and supplies a prior canonicality-testing approach the paper compares against.","marker":"Cognetta & Okazaki, 2024"},{"why":"Provides the GPT-2 model family used as the primary experimental subjects.","marker":"Radford et al., 2019"},{"why":"Provides the Llama 3 model family used to test whether canonicality improvements transfer across tokenizer implementations.","marker":"Llama Team, 2024"},{"why":"Supplies the Penn Treebank test split used for held-out likelihood experiments.","marker":"Marcus et al., 1993"},{"why":"Supplies the WikiText test split used for held-out likelihood experiments.","marker":"Merity et al., 2017"}],"fun_headline_variants":["Enforce canonical BPE tokens to cut LM log-loss","Zero out impossible BPE encodings for lower loss","Canonicality in token LMs improves held-out likelihood","Make LMs output only canonical BPE token strings","Condense LM probability to canonical BPE strings"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Enforce canonical BPE tokens to cut LM log-loss","Zero out impossible BPE encodings for lower loss","Canonicality in token LMs improves held-out likelihood","Make LMs output only canonical BPE token strings","Condense LM probability to canonical BPE strings"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.018189,"raw_usage":{"total_tokens":65664,"prompt_tokens":1029,"completion_tokens":64635,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":645,"completion_tokens_details":{"reasoning_tokens":64556}},"tokens_in":645,"tokens_out":64635,"duration_ms":305571,"temperature":1.0,"reasoning_tokens":64556,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T05:22:38.812996+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}