Research map / Learning theory and algorithms / Combinatorial and search optimization
A Partition Cover Approach to Tokenization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Formulates tokenization as a partition cover optimization problem, proves it NP-hard via vertex cover, and proposes the polynomial-time greedy tokenizer GreedTok that beats BPE and Unigram on compression and yields lower bits/byte when pre-training 1B LMs.
Problem
Tokenization (encoding strings into a fixed-size vocabulary to minimize token count) is usually framed as merge-based compression (BPE) or path-based likelihood (Unigram); the complexity and optimal formulation of tokenization as a direct selection problem is unclear.
Approach
Reformulate tokenization as choosing up to k candidate substrings that maximize the number of adjacent singleton pairs covered by a common token (equivalently minimizing total partitions), independent of bottom-up merge sequences; relax it to weighted maximum coverage and use a greedy selection (GreedTok) that adds the token with highest objective gain.
Key results
- GreedTok reduces tokens per word versus BPE by a mean of 2.88% and versus Unigram by 3.43% on arXiv, PubMed and wiki corpora.
- The 1B model trained on equal tokens (GTET) reaches 63.2 average benchmark accuracy versus 62.0 for the BPE model and 0.6989 vs 0.7066 bits/byte on Wikitext.
- GreedTok's objective reaches about 0.9(1-1/e) of the GreedWMC-based bound for large k, per the empirical ratio on RefinedWeb sampling.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GreedTok instead of BPE for tokenization | Tokenization · arXiv corpus (k=1000) | Tokens/Word: 1.837 -> 1.742 | Helped |
| Use GreedTok instead of Unigram for tokenization | Tokenization · PubMed corpus (k=2000) | Tokens/Word: 1.699 -> 1.603 | Helped |
| Use GreedTok rather than BPE as tokenizer, keeping training-token count equal | 1B-parameter transformer pretraining · DCLM Dedup benchmark average | Accuracy: 62.0 -> 63.2 | Helped |
| Use GreedTok rather than BPE as tokenizer, keeping dataset proportion equal | 1B-parameter transformer pretraining · DCLM Dedup benchmark average | Accuracy: 62.0 -> 62.5 | Helped |
| Use GreedTok rather than BPE as tokenizer, keeping training-token count equal | 1B-parameter transformer pretraining · Wikitext | bits/byte: 0.7066 -> 0.6989 | Helped |
| Use GreedTok rather than BPE as tokenizer, keeping dataset proportion equal | 1B-parameter transformer pretraining · Wikitext | bits/byte: 0.7066 -> 0.7028 | Helped |
| Use GreedTok rather than Unigram for tokenization | Tokenization · UN corpus at k=4000 | Tokens/Word: 1.193 -> 1.205 | Hurt |
| Use GreedTok rather than Unigram for tokenization | Tokenization · UN corpus at k=5000 | Tokens/Word: 1.148 -> 1.163 | Hurt |
Surprising findings
- GreedTok achieves better compression while also matching or improving downstream benchmark accuracy, contrary to prior reports that better compression can hurt performance.
- On the Unigram objective L, GreedTok is worse than Unigram in all tested settings, yet it selects more whole words and tokens common with Unigram than BPE does.
Limitations
- Pre-training comparisons are limited to BPE as the baseline and a single 1B model size, so scaling is not verified.
- No formal approximation guarantee for GreedTok; the 0.9(1-1/e) figure is empirical.
- Experiments focus on commonly used languages; low-resource languages were not evaluated.
Experimental setup
Datasets: UN arXiv wiki PubMed RefinedWeb DCLM Dedup
Benchmarks: ARC-c ARC-e HellaSwag OBQA PIQA SciQ BoolQ COPA LAMBADA RACE WinoGrande Wikitext
Metrics: tokens per word covering objective ratio bits per byte accuracy
Baselines: BPE Unigram GreedWMC
Builds on: Byte-Pair Encoding Unigram weighted maximum coverage greedy algorithm
Closest papers by meaning
- From Language Models over Tokens to Language Models over Characters (ICML 2025 · similarity 0.87)
- Explaining and Mitigating Crosslingual Tokenizer Inequities (NeurIPS 2025 · similarity 0.87)
- An Analysis of Tokenization: Transformers under Markov Data (NeurIPS 2024 · similarity 0.87)
- zip2zip: Inference-Time Adaptive Tokenization via Online Compression (NeurIPS 2025 · similarity 0.87)
- Getting the most out of your tokenizer for pre-training and domain adaptation (ICML 2024 · similarity 0.86)
- Scaffold-BPE: Enhancing Byte Pair Encoding for Large Language Models with Simple and Effective Scaffold Token Removal (AAAI 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.