Research map / Large language models / Reasoning and chain of thought
Language Models over Canonical Byte-Pair Encodings
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes enforcing BPE canonicality in token-level language models via test-time conditioning (global and local canonicalization with importance sampling) and a canonicalized architecture that is fine-tuned, showing log-loss improvements on PTB and WikiText for GPT-2 and Llama models.
Problem
Token-level language models assign nonzero probability to exponentially many noncanonical BPE token strings that the deterministic tokenizer would never produce, misallocating probability mass and degrading held-out likelihood.
Approach
Condition the token-level model on canonicality (global renormalization over canonical strings, approximated by a local per-token mask using an efficient bigram-based canonicality test), and alternatively build canonicality masks directly into the output layer of a transformer and fine-tune it.
Key results
- Global canonicalization reduces log-loss by -log Z for every model; on PTB the global method beats the local method for all models, while on WikiText local is better in all cases except GPT-2-medium.
- Canonicality by construction fine-tuning of GPT-2 small/medium with the canonicalized architecture gives consistent log-loss reductions over the unconstrained architecture for small lambda, though gains are smaller than with test-time conditioning.
- For GPT-2 the log-canonicality rate keeps decreasing with length, so the log-loss gain for GPT-2 is likely larger than estimated at the 1024-token cap.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Condition the model on generating only canonical token strings | GPT-2 and Llama models · Penn Treebank test | log-loss | Helped |
| Locally mask token choices that would make the output noncanonical | GPT-2 and Llama models · Penn Treebank test | log-loss | Helped |
| Condition the model on generating only canonical token strings | GPT-2 and Llama models · WikiText test | log-loss | Helped |
| Locally mask token choices that would make the output noncanonical | GPT-2 and Llama models · WikiText test | log-loss | Helped |
| Use global rather than local canonicalization | GPT-2 and Llama models · Penn Treebank test | log-loss | Helped |
| Use local rather than global canonicalization | GPT-2 and Llama models · WikiText test | log-loss | Mixed |
| Fine-tune on the target dataset | Original and canonicalized GPT-2 architectures · Penn Treebank and WikiText held-out data | log-loss | Helped |
| Use the canonicalized architecture instead of the original architecture during fine-tuning | GPT-2 small and GPT-2 medium · Penn Treebank and WikiText held-out data | log-loss | Helped |
| Use smaller regularization parameter values (ablation) | Fine-tuned GPT-2 architectures · Penn Treebank and WikiText held-out data | log-loss | Helped |
Surprising findings
- On WikiText, the locally canonicalized model (which warps the distribution) can achieve a larger log-loss reduction than the globally canonicalized model.
- Language models often assign higher probability to noncanonical encodings than to the canonical one (e.g., GPT-2 gives the canonical tokenization only 2.7% probability in one example).
Limitations
- Evaluation is limited to held-out log-loss; no measurement of sample quality or downstream task performance.
- Only BPE is studied; the bigram canonicality test ignores pre-tokenization, requiring hand-crafted overrides that can introduce false positives.
- Canonicality-by-construction experiments are proof-of-concept fine-tuning of only GPT-2 small and medium due to compute limits.
Experimental setup
Datasets: Penn Treebank WikiText
Benchmarks: Penn Treebank test WikiText test
Metrics: log-loss (bits/string)
Baselines: GPT-2 small GPT-2 medium GPT-2 large Llama-3.2-1B Llama-3.2-3B Llama-3.1-8B
Builds on: byte-pair encoding rejection sampling importance sampling
Closest papers by meaning
- Broken Tokens? Your Language Model can Secretly Handle Non-Canonical Tokenizations (NeurIPS 2025 · similarity 0.91)
- Exact Byte-Level Probabilities from Tokenized Language Models for FIM-Tasks and Model Ensembles (ICLR 2025 · similarity 0.90)
- An Analysis of Tokenization: Transformers under Markov Data (NeurIPS 2024 · similarity 0.89)
- From Language Models over Tokens to Language Models over Characters (ICML 2025 · similarity 0.89)
- The Foundations of Tokenization: Statistical and Computational Concerns (ICLR 2025 · similarity 0.88)
- From Bytes to Ideas: Language Modeling with Autoregressive U-Nets (NeurIPS 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.