Metraipolis › archive › dc_7a360c5186dd
The Price of Token Boundaries: Compression Certificates and Prediction — arXiv:2609.35869
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.35869
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T16:22:05.119Z
- SHA-256 of the archived text
84153be336afba6f3727a0a11819a7a0c1b0b261800383a7ddf431f61f4e37ad- Stable URL of this page
https://metraipolis.com/documento/dc_7a360c5186dd
How to cite
The Price of Token Boundaries: Compression Certificates and Prediction — arXiv:2609.35869 — arXiv (en), https://arxiv.org/abs/2609.35869 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7a360c5186dd (Metraipolis archive dc_7a360c5186dd, sha256 84153be336afba6f3727a0a11819a7a0c1b0b261800383a7ddf431f61f4e37ad)
BibTeX
@misc{dc7a360c5186dd,
title = {The Price of Token Boundaries: Compression Certificates and Prediction — arXiv:2609.35869},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.35869},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7a360c5186dd; sha256 84153be336afba6f3727a0a11819a7a0c1b0b261800383a7ddf431f61f4e37ad},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.35869. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Pre-tokenisation restricts which text fragments can become prediction units, but its compression cost is obscured when tokenisers are compared only under the same boundaries. We measure this cost by bounding the minimum token count from both sides, with and without a regular-expression boundary rule. Nonnegative prices on token occurrences yield a lower bound through shortest paths and vocabulary-budget selection; maximising over all prices recovers the linear programming relaxation, and an independent integer checker certifies the reported values. On English Wikipedia, boundaries increase the optimal token count by 28.3--36.8\%. Byte pair encoding lies 2.1\% above the constrained lower bound, but 10.9\% above the unrestricted bound. Compression and prediction favour different dictionaries: at 85M non-embedding parameters and matched training-token budgets, unrestricted fitting yields higher mean held-out bits per byte under a common unrestricted decoder in all 12 languages in the paired study and 11 of 12 under independent tuning and evaluation. To study intermediate boundary policies, we introduce boundary licences, which limit the vocabulary entries permitted to cross cuts and admit the same form of certificate. On separate English and Chinese fitting corpora, licensing 10\% of the vocabulary budget recovers 85.2\% and 100.0\% of the achieved token-count reduction from removing all cuts. These results quantify the compression cost of boundaries while separating it from the prediction quality of the resulting token units. Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-30 in cs.AI). Categorie arXiv: Artificial Intelligence (cs.AI) ; Computation and Language (cs.CL). Pagina del lavoro: https://arxiv.org/abs/2609.35869 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-07T15:54:53.437Z dalla pagina https://arxiv.org/catchup/cs.AI/2026-09-30?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).