The Compression Cost of Token Boundaries and Their Effect on Prediction

Summary

The study quantifies how pre-tokenisation boundaries affect both compression and prediction. By assigning nonnegative prices to token occurrences, it derives lower bounds on the minimum token count using shortest paths and vocabulary-budget selection; maximising over prices recovers a linear-programming relaxation, while an independent integer checker certifies the reported values. On English Wikipedia, regular-expression boundaries raise the optimal token count by 28.3% to 36.8%. Byte pair encoding is 2.1% above the constrained lower bound but 10.9% above the unrestricted one. The researchers then compare dictionaries under matched 85-million-non-embedding-parameter models and equal training-token budgets. Unrestricted fitting produces higher mean held-out bits per byte under a common unrestricted decoder in all 12 languages in the paired study, and in 11 of 12 languages under independent tuning and evaluation. To examine intermediate policies, the paper introduces boundary licences that allow only a limited portion of vocabulary entries to cross cuts. On separate English and Chinese fitting corpora, licensing 10% of the vocabulary budget recovers 85.2% and 100.0%, respectively, of the token-count reduction achieved by removing all cuts. The results show that dictionaries that compress text best need not be the ones that produce the best prediction units, while separating the compression cost of boundaries from the predictive quality of the resulting tokens.