The Price of Token Boundaries: Quantifying the Trade-off Between Compression Efficiency and Prediction Quality

The Hidden Cost of Tokenization Boundaries

Tokenization — the very first step in processing text for large language models — appears to be a mundane preprocessing detail. Yet it harbors a long-overlooked problem: pre-tokenization rules constrain which text spans can serve as prediction units, and the compression cost imposed by these constraints is routinely obscured when tokenizers are compared under identical boundary rules.

A recent arXiv paper (arXiv:2609.35869) confronts this issue head-on. The researchers set out to answer a fundamental question: how much compression efficiency do we actually sacrifice when regular-expression rules impose boundaries on text? Prior benchmarks, by always comparing tokenizers under the same boundary conditions, have never truly exposed this cost.

Pre-tokenization is the first stage of a modern tokenization pipeline. Before any token-splitting is learned, deterministic rules split raw text into segments that cannot be crossed. Take the tiktoken regex used in the GPT series: it enforces boundaries between spaces, punctuation, and alphanumeric characters, ensuring that "don't" can never be merged with adjacent words into a single token. These rules are typically motivated by linguistic intuition or engineering convenience — keeping numbers as standalone tokens, preventing bizarre cross-word merges, and so on. But because these boundaries are fixed before training data is ever processed, all subsequent BPE or Unigram learning operates within this constrained search space, with no opportunity to discover efficient cross-boundary tokens. The resulting compression loss is effectively baked into the baseline, invisible to conventional side-by-side comparisons.

Bounding the Cost of Tokenization Boundaries

The methodological core of the paper is bounding the minimum token count from both directions — measuring it both with and without boundary rules in place.

The researchers employ an elegant optimization framework: non-negative "prices" are assigned to token occurrences, and a combination of shortest-path search and vocabulary budget selection yields a lower bound; taking the maximum over all prices recovers the LP relaxation (linear programming relaxation); finally, an independent integer checker provides a certificate for the reported values.

This "compression certificate" design ensures verifiability — the reported optimal token counts are not estimates but quantitative results backed by rigorous upper and lower bounds. Such rigor is relatively rare in tokenization research.

Boundaries Inflate Token Counts by Nearly a Third

The empirical results on English Wikipedia are striking: boundary rules increase the optimal token count by 28.3% to 36.8%.

In other words, introducing regular-expression boundary splits alone forces models to process roughly one-third more tokens. This directly translates into longer sequences, higher computational costs, and greater context consumption.

For the widely used Byte Pair Encoding (BPE) algorithm, the paper provides a precise characterization: BPE sits only 2.1% above the constrained lower bound, but 10.9% above the unconstrained lower bound. This shows that BPE is already near-optimal within its given boundaries — but the boundaries themselves are the primary source of compression loss.

Byte Pair Encoding (BPE) is currently the dominant subword tokenization algorithm, introduced to NLP by Sennrich et al. in 2016. The core idea is to start from a single-byte (or single-character) vocabulary, then iteratively count the frequency of adjacent token pairs in the corpus and merge the most frequent pair into a new token, repeating until the vocabulary reaches a preset size. This greedy iterative process is simple and efficient, but inherently locally optimal — each merge considers only the currently most frequent pair without guaranteeing global minimization of token counts. This is precisely why the paper's finding that "BPE sits 2.1% above the constrained lower bound" is actually a compliment: BPE comes very close to the theoretical optimum within its boundary constraints. The remaining 10.9% gap reveals a structural limitation imposed by the boundary rules themselves — one that the BPE algorithm cannot overcome on its own.

Compression and Prediction Prefer Different Vocabularies

The paper's most thought-provoking finding is that it reveals a tension between compression efficiency and prediction quality: the two objectives favor different vocabularies.

Using a setting of 85 million non-embedding parameters with matched training token budgets, the researchers found that unrestricted fitting produced higher held-out bits per byte under a shared unconstrained decoder across all 12 languages studied; under independently tuned and evaluated conditions, 11 out of 12 languages showed the same result.

The key implication is clear: a vocabulary optimized for maximal compression is not necessarily the best choice for predictive modeling. Tokenizer design cannot focus solely on compression ratio — doing so may actually hurt a model's real-world prediction performance. This serves as a warning against the widely held intuition that "higher compression is always better."

Boundary Licences: A Practical Middle Ground

To explore strategies between the two extremes of "full boundaries" and "no boundaries," the paper proposes a boundary licences mechanism — it limits the number of vocabulary entries permitted to cross split points while still yielding compression certificates of the same form.

The experimental results are impressive: on separate English and Chinese fitting corpora, granting licences to just 10% of the vocabulary budget recovers 85.2% (English) and 100.0% (Chinese) of the token-count reduction achieved by removing all splits entirely.

This means there is no need to abandon boundary rules entirely. Selectively relaxing a small fraction of key vocabulary entries is enough to reclaim the vast majority — or even all — of the compression gains. For languages like Chinese, a 10% licence budget completely eliminates the compression loss caused by boundaries, a result particularly worth noting for practitioners working on Chinese NLP.

The boundary licences mechanism rests on a key insight: not all boundaries are equally costly. Within any vocabulary, only a small number of high-frequency cross-boundary spans — such as common prefixes, suffixes, or frequent collocations — contribute most significantly to compression efficiency. By issuing "licences" to these entries, allowing them to cross otherwise forbidden split points, substantial compression gains can be achieved at minimal cost to vocabulary flexibility. A 10% licence ratio means that in a vocabulary of 50,000 entries, roughly 5,000 entries are permitted to merge across boundaries, while the remaining 90% continue to respect the original boundary rules. This design is particularly engineering-friendly: there is no need to overhaul the entire tokenization pipeline. Adding a simple entry-level "licence flag" to an existing BPE framework can bring compression efficiency much closer to the unconstrained ideal, while preserving the engineering robustness that boundary rules provide for handling special characters, multilingual text mixing, and similar edge cases.

Implications for Tokenizer Design

The value of this research lies in transforming the "compression cost of tokenization boundaries" from vague intuition into quantifiable, certifiable numbers — and in clearly distinguishing that cost from the prediction quality of the resulting token units.

Several practical takeaways emerge:

• Tokenization boundaries are not free — they can increase token counts by more than 30%;
• Vocabularies optimized purely for compression may perform worse on prediction tasks, so evaluation must consider both dimensions;
• Boundary licences offer a pragmatic middle road, trading a small amount of flexibility for the recovery of most compression gains.

At a time when long contexts and inference costs are increasingly becoming bottlenecks, revisiting the efficiency of tokenization — the very starting point of the pipeline — may offer better returns than continuing to scale up model parameters.