Back to Home
arXiv AI··Papers & Tech

The Price of Token Boundaries: Compression Certificates and Prediction

中文摘要

本文研究了分词边界对压缩成本的影响,提出通过界定最小标记数,利用最短路径算法衡量成本并优化词表选择的方法。

English Summary

This paper investigates compression costs caused by token boundaries, proposing a method to bound token counts and optimize vocabulary selection using shortest path algorithms.

Original Excerpt

arXiv:2609.35869v1 Announce Type: new Abstract: 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 …