acceptodds
Under review as a conference paper at ICLR 2027

THE PRICE OF TOKEN BOUNDARIES: COMPRESSION CERTIFICATES AND PREDICTION

12 views

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. Non-negative 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 commonunrestricted 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 vocabulary entries permitted to 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% and 100.0% of the achieved token-count reduction from removing all cuts. These results quantify the compression cost of boundaries while separating it from the prediction quality of the resulting token units.

Primary area:
foundation or frontier models, including LLMs
Keywords:
okenization, Pre-tokenization, Vocabulary Optimization, Certified Compression, Language Modeling, Boundary Constraints, Lagrangian Relaxation, Boundary Licences

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_cMqsOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies the compression cost of pre-tokenisation boundaries and their effect on language-model prediction. It introduces an occurrence-price certificate that lower-bounds the minimum achievable token count through shortest-path computations and vocabulary selection. The authors prove that optimising these certificates recovers the LP relaxation and provide an independent integer-arithmetic checker.

Experiments across 12 languages show substantial compression costs from pre-tokenisation, including a certified 28.3-36.8% increase in optimal token count for English. However, vocabularies fitted without boundaries generally yield worse language-model prediction, despite achieving better compression. The authors validate this through multilingual experiments.

They introduce boundary licences, which allow a limited number of vocabulary entries to cross boundaries. Their experiments show that licensing 10% of the vocabulary recovers 85.2% and 100% of the achieved compression gains in English and Chinese, respectively.

Critical strengths

The paper provides certified bounds on how much compression is lost due to pre-tokenisation, rather than relying on comparisons between specific tokenizers. This is a meaningful contribution, given the substantial costs observed across languages.

Strong empirical evaluation - the multilingual experiments demonstrate that better compression does not necessarily improve prediction.

Critical weaknesses

The proposed intermediate boundary policies recover substantial compression gains, but their effect on language-model prediction is not tested. It remains unclear whether they offer a useful compression–prediction tradeoff.

Questions for authors

How does language-model prediction change with the boundary-licence budget? A comparison at 0%, 10%, and 100% would help establish whether intermediate policies recover compression gains while preserving prediction quality.

Reviewer_JAPyOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The authors investigate how much achievable compression is lost due to standard pretokenization schemes common in the tokenization literature. These pretokenization schemes prevent subword tokens from crossing certain boundaries, such as whitespace. The authors articulate a mathematical framework for finding a lower bound on the optimal (lowest) token count on a corpus with and without pretokenization restrictions and find that pretokenization increases the optimal token count by 28.3 to 36.8% on English text and 9.8 to 11.0% on Chinese text. They then perform real language modeling experiments on small Transformers that use or omit pretokenization boundaries, finding that the pretokenization boundary restrictions actually result in LMs with better held-out bits per byte on average across 12 languages. Finally, they introduce a "boundary licensing" experiment to test the effects of limiting boundary crossing to only a few tokens, finding that allowing boundary licensing on only 10% of the vocabulary can recover most compression.

Critical strengths
  1. The topic of understanding the effects of pretokenization and how it influences both the optimal compression of tokenizer and the downstream language modeling task is an important question for both tokenization and LM pre-training research.
  2. The authors include a comprehensive set of experiments including theoretical/mathematical bounds on token counts, several 85M-parameter LM pretraining runs, and evaluations across 12 languages.
Critical weaknesses

This paper was extremely hard to read. The authors introduce very strange wordings and vocabulary that are not standard or necessary for describing these tokenization concepts. It took substantial effort, longer than the average review, to understand the basic premise of the paper. If the readability could be improved, the concepts are much more straightforward than the authors make them seem. Overall, this paper needs a substantial rewrite in order to be eligible for conference acceptance.

Questions for authors

N/A

Reviewer_G63cOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates the compression cost of pre-tokenisation boundaries and its implications for language-model prediction. The authors derive occurrence-price certificates that bound optimal token counts, showing that regex boundaries increase the English compression optimum by 28.3–36.8%. Across multilingual experiments with a common decoder and matched training-token budgets, dictionaries fitted without boundaries compress better but generally yield worse held-out prediction. The paper also introduces boundary licences, demonstrating that permitting a small fraction of vocabulary entries to cross boundaries recovers most of the achieved compression gain.

Critical strengths
  1. The paper provides certified bounds on the compression cost of pre-tokenisation boundaries, distinguishing the cost of the constraint itself from the limitations of a particular vocabulary learner. The independent integer-arithmetic checker strengthens the reliability of these bounds.

  2. The multilingual experiments offer useful evidence that better compression does not necessarily improve language-model prediction. The common-decoder comparison and replication with independent tuning and evaluation strengthen this finding.

  3. Boundary licences provide a principled way to interpolate between constrained and unrestricted tokenisation. The results show that licensing a small fraction of vocabulary entries can recover most of the achieved compression gain.

Critical weaknesses
  1. The prediction experiments do not fully isolate the effect of boundary constraints during vocabulary fitting. Vocabulary-search effort differs between regimes, while matched training-token budgets produce different byte exposure. Although the additional controls are useful, these factors limit causal attribution of the observed prediction gap.

  2. Boundary licences are evaluated for compression but not language-model prediction. Consequently, the paper does not establish whether intermediate licence budgets can retain the prediction benefits of constrained fitting while recovering compression gains.

  3. The generality of the prediction findings remains uncertain. The main multilingual comparison uses an 85M-parameter model, while the broader scaling experiments use different comparison protocols and show smaller penalties at larger scales. Stronger evidence is needed to establish whether the same trade-off persists for larger models.

Questions for authors

Please see the weakness.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.