Language Models over Canonical Byte-Pair Encodings
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912420798136320 |
|---|---|
| author | Vieira, Tim Liu, Tianyu Pasti, Clemente Emara, Yahya DuSell, Brian LeBrun, Benjamin Giulianelli, Mario Gastaldi, Juan Luis O'Donnell, Timothy J. Cotterell, Ryan |
| author_facet | Vieira, Tim Liu, Tianyu Pasti, Clemente Emara, Yahya DuSell, Brian LeBrun, Benjamin Giulianelli, Mario Gastaldi, Juan Luis O'Donnell, Timothy J. Cotterell, Ryan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_07956 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Language Models over Canonical Byte-Pair Encodings Vieira, Tim Liu, Tianyu Pasti, Clemente Emara, Yahya DuSell, Brian LeBrun, Benjamin Giulianelli, Mario Gastaldi, Juan Luis O'Donnell, Timothy J. Cotterell, Ryan Computation and Language Formal Languages and Automata Theory Machine Learning 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. |
| title | Language Models over Canonical Byte-Pair Encodings |
| topic | Computation and Language Formal Languages and Automata Theory Machine Learning |
| url | https://arxiv.org/abs/2506.07956 |