The Price of Token Boundaries: compression certificates and prediction (arXiv:2609.35869v1)
This paper introduces a method to quantify the compression cost imposed by pre-tokenisation boundaries by bounding minimum token counts via nonnegative token prices, shortest-path certificates, and an LP relaxation verified by an integer checker. Empirical results on English Wikipedia and separate English/Chinese corpora show boundaries raise optimal token counts by 28.3–36.8%, BPE is 2.1% above the constrained lower bound (10.9% above the unrestricted bound), unrestricted fitting often yields better held-out bits-per-byte across languages, and a proposed ‘boundary licences’ scheme recovering most token-count reductions when allowing a small fraction of vocabulary entries to cross cuts.