Mainstream large language models rely on a tokenizer to encode text into a token sequence. Different tokenizers may yield token sequences of substantially different lengths for the same text. With a fixed model architecture, shorter token sequences correspond to lower inference time. We propose a tokenizer training approach named Counting and Filtering (CNF) and a text encoding algorithm called Min-Cost Encoding (MCE). MCE defines a cost function over a text segment, and determines the best segmentation by globally minimizing the overall segmentation cost. CNF builds a raw vocabulary by directly counting valid substrings, and then constructs the final vocabulary through a filtering step based on actual token usage when segmenting the training corpus with MCE. The CNF-MCE conbination offers several advantages over BPE, including higher token efficiency, greater scalability, and lower dependency. Across six text categories and two vocabulary-size groups, CNF-MCE consistently achieves better compression than the evaluated BPE tokenizers. With a 250K vocabulary, CNF-MCE increases compression rate by 26% and 30% on English web text over the o200k_base and qwen250k tokenizers. Experiments scaling the vocabulary to 1M entries on English web text demonstrate sustained improvements over BPE, with a token efficiency improvement of over 60% and vocabulary utilization rising from 52.9% to 96.9%. The MCE algorithm does not depend on a merge list (as in BPE) or token probability (as in UnigramLM), making it applicable to a wide range of vocabularies, including those built from BPE, UnigramLM, CNF, and others. Language models trained from scratch at the 1.8B and 8B scales achieve comparable average performance to models using the BPE tokenizers across 11 benchmarks. These results demonstrate that CNF-MCE can improve token efficiency significantly while maintaining competitive downstream performance.
Figures & tables
Group
Vocab. name
Construction
Size
Model series
Smaller (100k–160k)
llama128k
BPE
128k
Llama3.2 ( Meta, 2024 )
ds128k
BPE
128k
DeepSeek-V4 ( DeepSeek-AI, 2026 )
qwen152k
BPE
152k
Qwen2.5/3 ( Qwen et al., 2024 ; Yang et al., 2025 )
cl100k_base
BPE
100k
GPT-3.5/4 ( OpenAI, 2026 )
mix138k
CNF
138k
–
Larger (200k–250k)
o200k_base
BPE
200k
GPT-4o/4.1/4.5, o1, o3, o4 ( OpenAI, 2026 )
Table 1: Overview of the vocabularies used in our experiments.
Text type
llama128k
ds128k
qwen152k
cl100k_base
mix138k
Improvement over
ds128k
qwen152k
en-web
4.640
4.643
4.545
4.632
5.599
20.6%
23.2%
en-pdf
4.023
4.145
3.905
4.013
4.936
19.1%
26.4%
math
3.640
3.725
3.471
3.630
4.462
19.8%
28.6%
code
3.413
3.178
3.143
3.381
3.728
17.3%
18.6%
zh
1.240
1.696
1.553
0.872
1.812
6.8%
16.7%
Table 2: Compression performance in the Smaller-vocabulary group.
Text type
o200k_base
qwen250k
mm200k
mix250k
Improvement over
o200k_base
qwen250k
en-web
4.700
4.499
4.752
5.955
26.7%
32.4%
en-pdf
4.051
3.856
4.244
5.211
28.7%
35.1%
math
3.651
3.400
3.774
4.678
28.1%
37.6%
code
3.388
2.983
3.324
3.880
14.5%
30.1%
zh
1.311
1.703
1.758
1.963
49.7%
15.3%
Table 3: Compression performance in the Larger-vocabulary group.
Figure 1: Vocabulary scaling on en-web : (a) token efficiency and (b) vocabulary utilization after 100M output tokens per configuration. Higher is better in both panels. Vocabulary size uses a logarithmic axis; 1K denotes 1,000 entries and 1M denotes 1,024,000 entries.
Metric
qwen250k
mix250k
Compression and vocabulary usage
Fertility ↓
5.550
4.429
Token length ↑
3.832
4.718
Vocabulary utilization ↑
0.2147
0.2696
Compression rate (bytes/token) ↑
5.143
6.329
Token distributions and multilingual fairness
Table 4: Intrinsic evaluation with TokEval.
Text type
Token efficiency
MCE vs. BPE
FMM vs. BPE
FMM vs. MCE
BPE
FMM
MCE
Dist. (%)
Agree. (%)
Dist. (%)
Agree. (%)
Dist. (%)
Agree. (%)
en-web
222.5
222.1
221.6
3.64
97.53
7.30
94.78
5.95
95.60
math
297.6
297.2
296.6
3.61
96.88
6.54
94.02
5.52
94.95
code/python
278.3
278.0
276.4
11.21
87.50
21.48
70.91
16.4
78.26
zh
643.7
643.4
637.4
2.65
97.00
6.75
92.11
5.21
93.72
Table 5: Token efficiency and pairwise segmentation comparisons on the fixed qwen250k vocabulary.
Text type
Token efficiency
MCE vs. FMM
Boundary-crossing (%)
FMM
MCE
Dist. (%)
Agree. (%)
MCE
FMM
en-web
170.4
168.0
20.73
83.10
0
2.291
math/finemath
223.6
221.5
17.23
84.31
0
1.210
code/python
234.3
230.1
23.3
78.23
0
1.064
zh
510.6
509.3
11.62
88.32
0
0.019
Table 6: Compression and segmentation comparisons on the fixed mix250k vocabulary.
Benchmark
Phase-1
Decay phase
qwen152k
mix138k
qwen152k
mix138k
ARC
53.2
49.4
58.1
58.2
CommonsenseQA
39.6
38.7
38.5
36.1
GSM8K
0.7
2.1
17.9
20.6
HellaSwag
59.2
59.9
61.2
61.7
HumanEval
1.0
1.7
6.0
4.3
Table 7: Downstream performance of language models trained from scratch at the 1.8B scale with different vocabularies.
Benchmark
Phase-1
Decay phase
qwen152k
mix250k
qwen152k
mix250k
ARC
59.9
57.1
65.0
62.7
CommonsenseQA
41.8
41.6
41.4
42.9
GSM8K
1.2
6.1
20.8
38.7
HellaSwag
67.2
67.6
72.1
70.8
HumanEval
1.8
1.2
11.6
4.3
Table 8: Downstream performance of language models trained from scratch at the 8B scale with different vocabularies.
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Text type
Datasets and subsets
Used for
en-web
FineWeb-Edu ( Lozhkov et al., 2024a ) ; DCLM-Edu ( Allal et al., 2025 ) ; the common_crawl subset of Dolma3 ( Team Olmo et al., 2025 ) .
train & test
en-pdf
The olmocr_science_pdfs and rpj-proofpile-arxiv subsets of Dolma3 ( Team Olmo et al., 2025 ) ; peS2o ( Soldaini and Lo, 2023 ) .
test
math
FineMath ( Allal et al., 2025 ) ; Nemotron-CC-Math-v1 ( Mahabadi et al., 2025 ) .
train & test
code
The Stack v2 deduplicated release ( the-stack-v2-dedup ) ( Lozhkov et al., 2024b ) .
train & test
zh
FineWeb2-HQ ( Messmer et al., 2025 ) ; SkyPile-150B ( Wei et al., 2023 ) ; CCI4.0 ( BAAI/CCI4.0-M2-Base-v1 ) ( Liu et al., 2025b ) .
train & test
lang11
FineWeb2 ( Penedo et al., 2025 ) ; FineWeb2-HQ ( Messmer et al., 2025 ) ; Thai data from Mangosteen ( Phatthiyaphaibun et al., 2025 ) and WanJuanSiLu ( Yu et al., 2025 ) .
train & test
Appendix
Table 9: Data sources used in the tokenizer experiments. Dolma3 subsets refer to the dolma3_mix-5.5T-1125 release.
Vocab. size
BPE
CNF–MCE
CPT ↑
Utilization (%) ↑
CPT ↑
Utilization (%) ↑
1K
2.382
97.7
2.441
97.7
2K
2.800
98.8
2.970
99.0
4K
3.223
99.4
3.497
99.4
8K
3.644
99.6
4.093
99.6
16K
4.028
99.6
4.687
99.7
Appendix
Table 10: Vocabulary scaling on en-web with a 100M-token budget per configuration. CPT denotes characters per token; utilization is the percentage of vocabulary entries observed at least once. Higher is better for both metrics.
Text
BPE
FMM
MCE
␣autoregulation
␣autore ∥ g ∥ ulation
␣autore ∥ gul ∥ ation
␣auto ∥ reg ∥ ulation
␣pandemics
␣pand ∥ emics
␣pandemic ∥ s
␣pandemic ∥ s
␣inconceivable
␣incon ∥ ce ∥ ivable
␣incon ∥ ce ∥ ivable
␣inc ∥ once ∥ ivable
␣Modeller
␣Mod ∥ eller
␣Modelle ∥ r
␣Model ∥ ler
␣Trips
␣Tri ∥ ps
␣Trip ∥ s
␣Tr ∥ ips
␣mediate
␣med ∥ iate
␣media ∥ te
␣ ∥ mediate
Appendix
Table 11: Example tokenization results of various encoding algorithms operating on the qwen250k vocabulary
Text
BPE
FMM
MCE
␣were␣more␣likely␣to␣suffer
-
␣were␣more ∥ ␣likely␣to ∥ ␣suffer
␣were ∥ ␣more␣likely␣to ∥ ␣suffer
␣that␣approximately
-
␣that␣a ∥ pp ∥ rox ∥ imate ∥ ly
␣that ∥ ␣approximately
␣move␣together
-
␣move␣to ∥ get ∥ her
␣move ∥ ␣together
Double␣Digit␣Addition
-
Double ∥ ␣Dig ∥ it ∥ ␣Addition
Double ∥ ␣Digit ∥ ␣Addition
␣is␣to␣find␣the␣sum␣of␣the
-
is␣to ∥ ␣find␣the ∥ ␣sum␣of ∥ ␣the
is ∥ ␣to␣find ∥ ␣the␣sum␣of␣the
Appendix
Table 12: Example tokenization results of different encoding algorithms operating on the mix250k vocabulary
Configuration
1.8B
8B
Total parameters
1.89B
8.99B
Non-embedding parameters
1.61B
6.95B
Model dimension
2048
4096
MLP hidden dimension
6144
12288
Head dimension
128
128
Number of query heads
16
32
Appendix
Table 13: Configurations of the CNF–MCE models for downstream evaluation.
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.
Craig W. Schmidt, Michael Krumdick, Adam Wiemerslage +4
Kensho Technologies · Ben-Gurion University · MIT Cambridge, MA
Language models process and generate text sequentially in token units, and the tokenizer determines how much text each inference step covers. Under standard tokenization, a short English phrase such as "On the table." is usually produced as four separate predictions for the preposition (On), article (the), noun (table), and punctuation (.), where each consumes a sequence position and adds inference cost. We introduce CoBPE, a compositional tokenization approach that represents such phrases as a lexical base token (table) attached with a small set of reusable surface modifiers, composed in embedding space at input and predicted jointly at output. In controlled pretraining from scratch at 780M and 1.3B scales, CoBPE shortens sequences by 30% and improves average downstream performance by 1.2 points relative to standard BPE under matched training compute. Our results suggest that part of what is now expressed through token sequences can instead be modeled through structured representations, opening a broad design space for more token-efficient and capable language models.
We propose a novel algorithm for incremental Byte Pair Encoding (BPE) tokenization. The algorithm processes each input byte in worst-case O(log2t) time, leading to an overall complexity of O(nlog2t), where n is the input length and t is the maximum token length. The algorithm incrementally maintains BPE tokenization results for every prefix of the input text, implementing the standard BPE merge procedure defined by a fixed set of merge rules. This enables efficient partial tokenization in streaming settings. Functioning as a drop-in replacement for standard BPE, our approach achieves a speedup of up to ∼3× over Hugging Face's tokenizers, and demonstrates significant latency reductions over OpenAI's tiktoken on pathological inputs. We further introduce an eager output algorithm that enables streaming output, emitting tokens as soon as token boundaries are determined during incremental tokenization. Overall, our results demonstrate that BPE tokenization can be performed incrementally with strong worst-case guarantees, while providing practical latency benefits in modern large language model pipelines. Code: https://github.com/ModelTC/mtc-inc-bpe