# The Price of Token Boundaries: Compression Certificates and Prediction

arXiv: https://arxiv.org/abs/2609.35869 · HTML: https://mlsanity.com/paper/2609.35869/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 31 references that are in the map.
- First posted on arXiv 26 Sep 2026.

## Builds on (most cited first, 21 of 21)

- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing](https://mlsanity.com/paper/1808.06226/) (2018)
- [The FineWeb Datasets: Decanting the Web for the Finest Text Data at Scale](https://mlsanity.com/paper/2406.17557/) (2024)
- [Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates](https://mlsanity.com/paper/1804.10959/) (2018)
- [BLiMP: The Benchmark of Linguistic Minimal Pairs for English](https://mlsanity.com/paper/1912.00582/) (2019)
- [Byte Pair Encoding is Suboptimal for Language Model Pretraining](https://mlsanity.com/paper/2004.03720/) (2020)
- [MEGABYTE: Predicting Million-byte Sequences with Multiscale Transformers](https://mlsanity.com/paper/2305.07185/) (2023)
- [Byte Latent Transformer: Patches Scale Better Than Tokens](https://mlsanity.com/paper/2412.09871/) (2024)
- [FineWeb2: One Pipeline to Scale Them All -- Adapting Pre-Training Data Processing to Every Language](https://mlsanity.com/paper/2506.20920/) (2025)
- [Parallelizing the dual revised simplex method](https://mlsanity.com/paper/1503.01889/) (2015)
- [Tokenization Is More Than Compression](https://mlsanity.com/paper/2402.18376/) (2024)
- [SuperBPE: Space Travel for Language Models](https://mlsanity.com/paper/2503.13423/) (2025)
- [Tokenization and the Noiseless Channel](https://mlsanity.com/paper/2306.16842/) (2023)
- [MambaByte: Token-free Selective State Space Model](https://mlsanity.com/paper/2401.13660/) (2024)
- [Boundless Byte Pair Encoding: Breaking the Pre-tokenization Barrier](https://mlsanity.com/paper/2504.00178/) (2025)
- [OpenCSG Chinese Corpus: A Series of High-quality Chinese Datasets for LLM Training](https://mlsanity.com/paper/2501.08197/) (2025)
- [Two Counterexamples to Tokenization and the Noiseless Channel](https://mlsanity.com/paper/2402.14614/) (2024)
- [Entropy-Driven Pre-Tokenization for Byte-Pair Encoding](https://mlsanity.com/paper/2506.15889/) (2025)
- [Tokenisation via Convex Relaxations](https://mlsanity.com/paper/2605.22821/) (2026)
- [Faster Superword Tokenization](https://mlsanity.com/paper/2604.05192/) (2026)
- [Joint Optimization for Greedy Longest-match Tokenization](https://mlsanity.com/paper/2607.23362/) (2026)

## Abstract (arXiv)

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.