The Price of Token Boundaries: Compression Certificates and Prediction

Yuhao Du; Shunian Chen

cs.AISep 26, 2026

The Price of Token Boundaries: Compression Certificates and Prediction

Authors: Yuhao Du, Shunian Chen

Organizations: The Chinese University of Hong Kong, Shenzhen · Shenzhen Loop Area Institute

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 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.

Figures & tables

Figure 1: A compression advantage need not improve prediction. (a) A cut removes crossing candidate occurrences; a licence lets a token cross it. (b) English compression optima, enclosed by feasible vocabularies and integer-checked lower bounds (

K{=}32768

L{=}16

, Wikipedia); the value axis is broken. Squares mark BPE’s achieved compression (

4.551

and

5.697

bytes per token); the annotated tax interval is

28.3

–

36.8\%

. (c) English test bit rates from three paired LM seeds; the value axis is broken. Both arms use unrestricted Viterbi encoding, with dictionaries fitted with or without regex boundaries. The unrestricted fitted dictionary has higher bit rate in each seed. In panels (b) and (c), blue marks the regex-constrained arm and gold the unrestricted arm. Compression certificates and test losses refer to their respective evaluation corpora.

	English		Chinese
Method	Regex	None	Regex	None
Optimum: upper ceiling	4.642	6.314	4.593	5.084
SlotPrice	4.616 (0.6)	5.958 (6.0)	4.582 (0.3)	5.045 (0.8)
BPE	4.551 (2.1)	5.697 (10.9)	4.545 (1.1)	4.978 (2.2)
Two-stage BPE	–	5.898 (7.1)	–	4.967 (2.4)
Unigram	2.894 (60.4)	5.735 (10.1)	4.006 (14.7)	4.787 (6.3)

Table 1: Removing cuts changes the compression optimum. Bytes per token (higher is better), with token-count gap to the integer-checked lower bound in parentheses (%), rounded upwards. The italic row is a conservative upper ceiling on achievable bytes per token, rounded upwards. Two-stage BPE uses an unconstrained merge curriculum and has no regex-constrained entry (–). Unigram optimizes likelihood, a different objective from minimum token count. English and Chinese Wikipedia,

K=32768

L=16

, approximately

42

MB per language; all methods use minimum-count encoding under the indicated cuts.

Figure 2: Compression cost and test prediction cost across languages. (a) Certified intervals for the optimal regex tax on Wikipedia; open circles show the corresponding achieved vocabulary ratios. (b) Paired test-bit-rate difference between unrestricted and regex-trained SlotPrice dictionaries after within-seed rate selection, with unadjusted

95\%

paired-

t

intervals over three seeds per language; filled markers are Holm-significant at

0.05

. Blue marks the compression measurements of panel (a); gold marks the prediction contrast of panel (b). The panels use their respective corpora and protocols; rows align the language-specific measurements from the two studies. Languages share one ordering, sorted by the certified lower endpoint of the panel-(a) interval. The two costs rank the languages differently: Vietnamese pairs the highest certified tax with a prediction penalty below the panel median, while Arabic pairs the largest prediction penalty with a certified tax below the panel median (Tables 3 and 10 ).

Language	Token blocks	Byte history	Sliding context
English	$+10.44\,\pm\,1.69$	$+9.90\,\pm\,1.19^{\dagger}$	$+10.68\,\pm\,1.81$
German	$+11.06\,\pm\,0.84^{\dagger}$	$+9.61\,\pm\,0.74^{\dagger}$	$+11.36\,\pm\,0.85^{\dagger}$
Russian	$+7.45\,\pm\,1.77$	$+5.75\,\pm\,1.62$	$+7.94\,\pm\,1.83$
Finnish	$+6.41\,\pm\,1.03$	$+6.01\,\pm\,0.70^{\dagger}$	$+6.57\,\pm\,1.11$
Turkish	$+8.37\,\pm\,0.69^{\dagger}$	$+6.88\,\pm\,0.59^{\dagger}$	$+8.84\,\pm\,0.67^{\dagger}$
Vietnamese	$+3.42\,\pm\,0.58$	$+3.78\,\pm\,0.48^{\dagger}$	$+3.44\,\pm\,0.56$

Table 2: Independent tuning preserves the average prediction penalty. Relative test bits-per-byte change (%) from the regex-fitted to the unrestricted dictionary; positive values favor the regex-fitted dictionary. Entries are paired means

\pm

standard deviations over three evaluation seeds, disjoint from the two tuning seeds.

\dagger

marks a two-sided paired test passing Holm correction over twelve languages within the indicated evaluation mode (

\alpha=0.05

Figure 3: Small licence budgets recover most of the achieved endpoint gain. Compression recovery as the boundary-licence budget grows, at

K=32{,}768

multibyte slots and

L=16

; the fitting corpora contain 8,434,722 English and 8,415,699 Chinese bytes. (a) English. (b) Chinese. Solid curves: achieved share of the endpoint token-count reduction, comparing exported occurrence-aware vocabularies. Dashed curves and shaded wedge: certified lower bound on the recovered share of the optimal endpoint gain (Equation 13 ); at every interior budget the certified upper bound is

100\%

. Recovery is exactly

0\%

q=0

and

100\%

q=K

by definition. These are optimisation bounds, not sampling uncertainty. The highlighted column marks the

10\%

licence budget. Tested budgets are equally spaced for display; connecting lines do not interpolate certificates.

Appendix figures & tables17 assets

Supplementary material from the paper’s appendix.

Appendix

	Regex		None				Tax (%)
Language	SlotPrice	BPE	SlotPrice	BPE	Two-stage	Unigram	Interval
English	4.616	4.551	5.958	5.697	5.898	5.735	28.3–36.8
German	4.823	4.714	6.031	5.641	5.845	5.622	24.0–33.3
Russian	7.203	7.007	9.012	8.422	8.459	8.288	24.1–37.1
Finnish	4.939	4.792	6.190	5.794	5.891	5.729	24.0–35.8
Turkish	4.957	4.863	6.330	5.776	6.077	5.928	26.8–34.6

Appendix

Table 3: Compression scores and optimal-tax intervals. All entries except the last column are achieved bytes per token under minimum-count encoding. Bold marks the highest achieved value within each language and regime. The final column is the outward-rounded certified optimal regex tax (%). Two-stage denotes the local BPE curriculum. Every language uses its own Wikipedia corpus and a common budget of

32768

non-byte entries; no cross-language byte-rate comparison is implied.

$B$	$d$	$L$	$K$	$\|\mathcal{C}\|$	LP	Uniform (%)	Occurrence (%)
1000	100	6	20	3k	660.0	91.6	99.99
1000	50	8	30	5k	570.0	86.3	99.79
1500	100	10	30	9k	880.0	86.5	99.82
2000	100	6	40	5k	1167.5	86.1	99.97
2000	100	8	40	9k	1124.2	85.9	99.90
2000	200	6	30	6k	1256.0	88.4	99.89

Appendix

Table 4: Checked dual values recover the full LP reference closely.

B

is corpus bytes and

d

is document length in bytes. Uniform and occurrence-price bounds are evaluated exactly at dyadic prices; recovery percentages use the unrounded rational lower bound and are rounded down. The occurrence-price result is the better of two 4000-step searches. LP and integer optima are the reference HiGHS ( Huangfu and Hall, 2018 ) solves, with numerical solver tolerances. Below, relaxation, primal and dual gaps are

100(\mathrm{OPT}/\mathrm{LP}-1)

100(\mathrm{UB}/\mathrm{OPT}-1)

and

100(\mathrm{LP}/\mathrm{LB}-1)

; their ratio factors multiply.

lang	$K$	$B/K$	bound $\pi$	bound $\varnothing$	achieved $\tau$	certified $\tau$	BPE gap $\pi\,/\,\varnothing$
English
	4096	10240	3.699	4.542	10.7%	4.6–30.0%	9.8% / 23.7%
	8192	5120	4.056	5.134	15.1%	11.4–30.7%	6.6% / 19.7%
	32768	1280	4.642	6.314	29.1%	28.3–36.8%	2.1% / 10.9%
	131072	320	4.994	8.006	54.5%	53.6–61.3%	1.3% / 11.9%
	ws 32768	1280	5.058	6.314	19.0%	17.8–26.1%	3.1% / –

Appendix

Table 5: Vocabulary-budget sweep at

L{=}16

42

MB per language.

B/K

is corpus bytes per vocabulary slot; bound columns are certified ceilings in bytes per token. Achieved tax and its certified two-sided interval use Proposition 14 . BPE gaps are listed for regex and regex-free regimes. ‘ws’ is a whitespace-only constraint at the indicated budget.

regex (deployed in)	$\bar{\ell}_{\pi}$	achieved	certified $\tau_{\pi}$	note
o200k / GPT-4o style	5.07	29.1%	28.3–36.8%
r50k (GPT-2)	5.18	26.0%	25.3–33.5%
cl100k (GPT-3.5/4)	5.05	29.2%	28.5–37.0%
LLaMA-3	5.05	29.2%	28.5–37.0%	$\equiv$ cl100k

Appendix

Table 6: Pre-tokenisation tax under deployed regex definitions on the same English headline instance. Each constrained vocabulary and bound is computed independently. cl100k and LLaMA-3 induce identical cuts on this corpus, so their rows are one measurement and their certified intervals coincide. ‘

\bar{\ell}_{\pi}

’ is the mean induced pretoken length in bytes.

Language	Encoder	$K$	Native	Cuts	No cuts
English	o200k_base	195,757	4.474	4.501	4.508
English	cl100k_base	99,200	4.408	4.437	4.444
Chinese	o200k_base	195,757	3.145	3.149	3.177
Chinese	cl100k_base	99,200	2.144	2.147	2.164

Appendix

Table 7: Released encoders and minimum-count segmentation on approximately

126

MB per language. Values are achieved bytes per token (higher is better).

K

counts retained multibyte vocabulary entries of length at most

L=16

. Native uses the released encoder; the last two columns use minimum-count segmentation with common o200k-style cuts or no cuts. Removing tokens longer than

L

increases the unrestricted minimum token count by at most

0.022\%

in these measurements. No optimization bound is used in this comparison.

Dual objective relative to the full optimizer (%; higher is better)
Variant	English	Time	Chinese	Time
Uniform prices	85.76	–	88.91	–
Without preconditioning	85.76	153	88.91	134
Without momentum	95.67	287	98.14	271
Without averaging	100.00	314	100.00	265
Full optimizer	100.00	305	100.00	294

Appendix

Table 8: Algorithm diagnostics on unrestricted English and Chinese instances,

K=32768

L=16

, approximately

16.8

MB per language, and 400 dual iterations. Values use the recorded floating-point dual objective; they are optimization diagnostics, not independent integer certificates. The primal gap is

100(\mathrm{UB}/\mathrm{LB}-1)

relative to the full-optimizer objective. Each setting has one recorded run on 40 CPU threads; times are seconds for the indicated optimizer or individual primal stage. Uniform-price initialization and active-set timings are not reported. The largest active sets contain 16,657,541 English and 16,777,216 Chinese types.

Arm	Vocabulary construction	LM encoding boundaries	Stream/evaluation decoder
BPE with regex	Native BPE, regex pieces	Serialised regex	Native ranked merges
BPE without regex	Native BPE, complete documents	None	Native ranked merges
SlotPrice π	SlotPrice , regex-constrained occurrences	None	Minimum-count Viterbi
SlotPrice	SlotPrice , unrestricted occurrences	None	Minimum-count Viterbi
Two-stage BPE	Locally trained two-stage merge adaptation	None	Minimum-count Viterbi
Unigram	Likelihood-trained byte vocabulary	None	Minimum-count Viterbi

Appendix

Table 9: Decoder protocol of the LM experiments. “Regex” in the construction column means that vocabulary fitting restricts candidate occurrences. A regex-trained byte vocabulary does not itself impose boundary masks at encoding time. The released SuperBPE artefact retains its serialised tokeniser pipeline.

Language	$\pi$	$\varnothing$	Change (%)	$95\%$ interval	Holm
English	1.1588	1.3405	+15.68	[+13.19, +18.18]	Yes
German	1.1773	1.3292	+12.92	[+1.78, +24.06]	No
Russian	0.6245	0.6964	+11.53	[+9.12, +13.93]	Yes
Finnish	1.2412	1.3619	+9.73	[+6.72, +12.73]	No
Turkish	1.0826	1.1915	+10.06	[+3.66, +16.46]	No
Vietnamese	0.8965	0.9428	+5.21	[-3.97, +14.38]	No

Appendix

Table 10: Held-out test results for the paired fitted-dictionary comparison. SlotPrice dictionaries are trained with (

\pi

) or without (

\varnothing

) the regex; both use document-level Viterbi encoding. Columns show mean test bits per byte, paired relative change (%), and its

95\%

paired-

t

interval over three seeds. The final column tests the twelve language contrasts using two-sided paired tests and Holm correction at

0.05

Setting	Contrast	Effect	Replicates	Summary
$85$ M, 12 languages	vs. SlotPrice π , test bits/byte	$+9.25\%$	3	$4.96$
$996$ M, $K{=}200$ k	vs. BPE, test bits/byte	$+4.58\%$	1	–
$387$ M, $K{=}200$ k, matched bytes	vs. SlotPrice π , BLiMP	$-4.5$ pts	2	–
$1.88$ B, $K{=}200$ k, $D{=}20N$	vs. BPE, BLiMP	$-3.3$ pts	2	unresolved

Appendix

Table 11: The prediction penalty under scale and budget controls. Contrasts of SlotPrice against the indicated reference arm, from the paired

12

-language

85

M panel to the

1.88

B English rung. Test bits-per-byte entries are relative increases; BLiMP entries are accuracy-point differences. The summary column reports the standard deviation across the

12

per-language mean contrasts (row one); the

1.88

B summary concerns whether the deficit continues to attenuate, using a descriptive band twice the root-sum-square of the arm checkpoint standard deviations. Replicates are training seeds except for the

1.88

B row, which counts checkpoints. The

996

M selected-rate test entry uses one seed per arm, and the

387

M matched-bytes contrast’s budget response is unresolved at 2 seeds per cell (Appendix C ). The

387

M matched-token difference against SlotPrice π is

-3.6

points. For the

1.88

B comparison against BPE, the

996

M reference difference is

-3.8

points.

Figure 4: English size ladder at

629{,}145{,}600

training tokens (

800

steps),

K=32768

non-byte entries and seed

1234

: (a) validation bits per byte and (b) loss relative to BPE with regex. Each point uses the best validation rate for that arm and model size.

Figure 5: English (top) and Chinese (bottom) validation bits per byte against training tokens (left) and estimated byte exposure (right). All curves use an

85

M non-embedding-parameter Transformer (12 layers, width 768, 12 heads),

K=32768

non-byte entries (

33{,}152

padded), a

2048

-token context, seed

1234

and shared initial rate

1.2\times 10^{-3}

. Exposure equals training tokens times mean training bytes per token, including repeated sampling; losses use mean validation bytes per token. Table 9 specifies the decoders.

Figure 6: Paired SlotPrice minus SlotPrice π BLiMP accuracy differences. (a) Field means and standard deviations across paired seed contrasts. (b) The five most negative and five most positive

996

M phenomenon-level contrasts (blue diamonds), linked to their

85

M counterparts (open grey circles); the rug above shows all 67 phenomena at both scales, placing the selected extrema in the full distribution. These selected extrema are exploratory.

English
$q$	$\|W\|$	achieved	ceiling	held-out	cross (%)	rare (%)	$H_{0}$
0	0	4.746	5.059	4.539	0.0	11.2	10.56
655	655	5.566	6.274	5.343	20.0	13.0	12.04
1,638	1,638	5.788	6.509	5.537	25.1	13.7	12.43
3,276	3,276	5.961	6.711	5.686	28.5	15.0	12.74
8,192	8,192	6.178	6.958	5.834	33.0	17.4	13.14

Appendix

Table 12: Boundary-licence frontier diagnostics at

K=32{,}768

L=16

. The cap

q

and used licence count

|W|

can differ. Fitting bytes per token are bracketed by the achieved vocabulary and certified ceiling, rounded downwards and upwards respectively. The remaining columns use disjoint held-out records totalling 1,107,737 English and 1,060,126 Chinese bytes. “Cross” is the percentage of emitted tokens crossing at least one regex cut; “rare” is token mass on types observed at most five times in that held-out slice;

H_{0}

is empirical unigram entropy in bits per token. These diagnostics are not neural losses.

Language	$q$	achieved (%)	optimal gain (%)
English	655	61.6	$\geq 30.4$
English	1,638	75.3	$\geq 42.1$
English	3,276	85.2	$\geq 50.5$
English	8,192	96.9	$\geq 60.5$
Chinese	655	84.2	$\geq 24.1$
Chinese	1,638	98.3	$\geq 37.1$

Appendix

Table 13: Recovery of the endpoint token-count reduction at interior budgets. The achieved ratio compares exported vocabularies. The certified interval encloses the fraction of the optimal endpoint gain recovered at that budget, using Equation 13 ; endpoints are rounded outwards. Its upper endpoint is

100\%

, so the final column prints the certified lower endpoint. At the omitted endpoints

q=0

and

q=K

, recovery is exactly

0\%

and

100\%

by definition.

English
	Random/regex change (%)		Held-out bytes/token		FIT crossing (%)
$q$	achieved	optimal interval	regex	random	regex	random
0	+48.7	[47.1,53.5]	3.803	2.743	0.0	26.6
163	+47.1	[15.2,57.0]	4.169	3.018	13.2	26.4
409	+42.9	[14.9,52.3]	4.282	3.179	16.9	27.6
819	+37.6	[12.0,46.8]	4.360	3.344	20.0	28.5

Appendix

Table 14: Cut-placement control at

K=8{,}192

L=16

, with 2,098,205 English and 2,136,886 Chinese fitting bytes. Random cuts permute each document’s regex-piece lengths in Unicode characters, preserving cut count and the character-length multiset; byte-length multisets can differ. The achieved and optimal columns give

100(\mathrm{tokens}_{\rm random}/\mathrm{tokens}_{\rm regex}-1)

for fitting vocabularies and optima respectively. Certified interval endpoints are rounded outwards. At

q=K

the optimal token-count change is exactly zero because both feasible sets are unrestricted, although finite-search vocabularies can differ. Crossing rates use the same linguistic regex cuts for both arms; they describe fitting segmentations, not neural prediction.

	Unrestricted		Regex-fitted
Language	Grid	Rate	Grid	Rate
English	$A$	0.6	$B$	2.4
German	$A$	0.6	$B$	2.4
Russian	$A$	1.2	$B$	2.4
Finnish	$B$	2.4	$B$	2.4
Turkish	$A$	0.6	$B$	2.4

Appendix

Table 15: Learning-rate grids and selected rates for the independent replication. All rates are in units of

10^{-3}

. The grids are

A=\{0.3,0.6,1.2,2.4\}

B=A\cup\{4.8,9.6\}

, and

H=\{0.009375,0.01875,0.0375,0.075,0.15\}

. Every grid point uses two tuning seeds. The selected rate minimizes their mean validation bits per byte and lies strictly inside its grid. Three disjoint seeds provide test measurements.

Comparison	Context	Relative change (%) / status	Holm $p$
English	Token blocks	10.44 [6.23, 14.64]	0.060
Chinese	Token blocks	4.62 [1.96, 7.29]	0.060
German	Token blocks	11.06 [8.99, 13.14]	0.021
Finnish	Token blocks	6.41 [3.85, 8.97]	0.060
Russian	Token blocks	7.45 [3.07, 11.84]	0.060
Japanese	Token blocks	3.36 [1.74, 4.97]	0.060

Appendix

Table 16: Independent tuning and evaluation: paired test contrasts. Changes are

100(\mathrm{bpb}_{\varnothing}/\mathrm{bpb}_{\pi}-1)

; positive values favor the regex-fitted dictionary. Entries give the mean and two-sided

95\%

paired-

t

interval over three evaluation seeds, disjoint from the two tuning seeds. Holm adjustment covers twelve languages separately within each context mode. Token blocks use 2048-token contexts; byte history uses a physical whole-token suffix of at most 1024 bytes per target; sliding contexts use strided overlapping windows.

Explore similar work

Tokenization with Split Trees
May 21, 2026Craig W. Schmidt, Michael Krumdick, Adam Wiemerslage +4Token Efficiency Subword Tokenization
Kensho Technologies · Ben-Gurion University · MIT Cambridge, MA
You Can Learn Tokenization End-to-End with Reinforcement Learning
Feb 15, 2026Sam Dauncey, Roger WattenhoferSubword Tokenization LLM Training
Department of Electrical Engineering, ETH Zurich, Zurich, Switzerland.
Compute Optimal Tokenization
May 2, 2026Tomasz Limisiewicz, Artidoro Pagnoni, Srini Iyer +6Language Model Scaling Laws Efficient Language Model Training
1FAIR at Meta · University of Washington

May 21, 2026J/K move · Enter open · S save

Tokenization with Split Trees

Craig W. Schmidt, Michael Krumdick, Adam Wiemerslage, Seth Ebner+3

Kensho Technologies · Ben-Gurion University · MIT Cambridge, MA

Token Efficiency Subword Tokenization Integer Linear Programming

Open paper AskPDF arXiv

We introduce Tokenization with Split Trees (ToaST), a subword tokenization method that directly optimizes compression under a new recursive inference procedure. ToaST greedily splits each pretoken into a full binary tree using precomputed byte n-gram counts, independent of any vocabulary. Given a vocabulary, inference recursively descends each split tree and emits the first in-vocabulary node reached on each path. Vocabulary selection is formulated as an Integer Program (IP) that minimizes the total token count over all split trees under this inference procedure. The Linear Programming (LP) relaxation is near-integral in practice, yielding provably near-optimal vocabularies, with training time empirically scaling quadratically in the number of split trees. On English text, ToaST reduces token counts by more than 11% compared to BPE, WordPiece, and UnigramLM at vocabulary sizes of 40,960 and above, reducing the number of inference tokens for models using this tokenizer, thus extending the effective context length. ToaST also uses common single-byte tokens less frequently than these baselines, leading to a substantial improvement in Renyi efficiency. In experiments training 1.5B parameter language models, ToaST achieves the highest CORE score, outperforming baselines by 2.6%--7.6%, with significance for two of three, and scoring best on 13 of 22 individual tasks.

Abstract

Explore similar work

Tokenization with Split Trees

You Can Learn Tokenization End-to-End with Reinforcement Learning

Compute Optimal Tokenization