Pre‑tokenisation restricts which text fragments may become prediction units, yet its compression cost is often hidden when tokenisers are compared only under identical boundaries. We measure this cost by bounding the minimum token count from both sides, with and without a regular‑expression boundary rule.
Assigning non‑negative prices to token occurrences yields a lower bound via shortest‑path computation and vocabulary‑budget selection; maximising over all price assignments recovers the linear‑programming relaxation, and an independent integer checker certifies the reported values.
On English Wikipedia, imposing boundaries raises 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 unconstrained bound. Compression and prediction favour different dictionaries: with 85 M non‑embedding parameters and matched training‑token budgets, unrestricted fitting yields higher mean held‑out bits per byte in all 12 languages of the paired study and in 11 of 12 languages under independent tuning and evaluation.
To explore intermediate boundary policies, we introduce boundary licences, which limit which vocabulary entries may 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% (English) and 100.0% (Chinese) of the token‑count reduction achieved by removing all cuts.
These results quantify the compression cost of boundaries while separating it from the prediction quality of the resulting token units.
Review