# Tokenization with Split Trees

arXiv: https://arxiv.org/abs/2605.22705 · HTML: https://mlsanity.com/paper/2605.22705/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 50 references that are in the map.
- First posted on arXiv 21 May 2026.

## Builds on (most cited first, 30 of 32)

- [Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation](https://mlsanity.com/paper/1609.08144/) (2016)
- [Improving Neural Machine Translation Models with Monolingual Data](https://mlsanity.com/paper/1511.06709/) (2015)
- [Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates](https://mlsanity.com/paper/1804.10959/) (2018)
- [DataComp-LM: In search of the next generation of training sets for language models](https://mlsanity.com/paper/2406.11794/) (2024)
- [How Good is Your Tokenizer? On the Monolingual Performance of Multilingual Language Models](https://mlsanity.com/paper/2012.15613/) (2020)
- [Byte Pair Encoding is Suboptimal for Language Model Pretraining](https://mlsanity.com/paper/2004.03720/) (2020)
- [Do All Languages Cost the Same? Tokenization in the Era of Commercial Language Models](https://mlsanity.com/paper/2305.13707/) (2023)
- [CulturaX: A Cleaned, Enormous, and Multilingual Dataset for Large Language Models in 167 Languages](https://mlsanity.com/paper/2309.09400/) (2023)
- [Parallelizing the dual revised simplex method](https://mlsanity.com/paper/1503.01889/) (2015)
- [Tokenization Is More Than Compression](https://mlsanity.com/paper/2402.18376/) (2024)
- [Getting the most out of your tokenizer for pre-training and domain adaptation](https://mlsanity.com/paper/2402.01035/) (2024)
- [Nemotron-CLIMB: CLustering-based Iterative Data Mixture Bootstrapping for Language Model Pre-training](https://mlsanity.com/paper/2504.13161/) (2025)
- [Superbizarre Is Not Superb: Derivational Morphology Improves BERT's Interpretation of Complex Words](https://mlsanity.com/paper/2101.00403/) (2021)
- [SuperBPE: Space Travel for Language Models](https://mlsanity.com/paper/2503.13423/) (2025)
- [Unpacking Tokenization: Evaluating Text Compression and its Correlation with Model Performance](https://mlsanity.com/paper/2403.06265/) (2024)
- [Tokenization and the Noiseless Channel](https://mlsanity.com/paper/2306.16842/) (2023)
- [MYTE: Morphology-Driven Byte Encoding for Better and Fairer Multilingual Language Modeling](https://mlsanity.com/paper/2403.10691/) (2024)
- [Morphology Matters: A Multilingual Language Modeling Analysis](https://mlsanity.com/paper/2012.06262/) (2020)
- [Greed is All You Need: An Evaluation of Tokenizer Inference Methods](https://mlsanity.com/paper/2403.01289/) (2024)
- [Boundless Byte Pair Encoding: Breaking the Pre-tokenization Barrier](https://mlsanity.com/paper/2504.00178/) (2025)
- [A Bit of a Problem: Measurement Disparities in Dataset Sizes Across Languages](https://mlsanity.com/paper/2403.00686/) (2024)
- [Parity-Aware Byte-Pair Encoding: Improving Cross-lingual Fairness in Tokenization](https://mlsanity.com/paper/2508.04796/) (2025)
- [How Much is Enough? The Diminishing Returns of Tokenization Training Data](https://mlsanity.com/paper/2502.20273/) (2025)
- [The Token Tax: Systematic Bias in Multilingual Tokenization](https://mlsanity.com/paper/2509.05486/) (2025)
- [Compositional Representation of Morphologically-Rich Input for Neural Machine Translation](https://mlsanity.com/paper/1805.02036/) (2018)
- [BPE Stays on SCRIPT: Structured Encoding for Robust Multilingual Pretokenization](https://mlsanity.com/paper/2505.24689/) (2025)
- [Tokenisation is NP-Complete](https://mlsanity.com/paper/2412.15210/) (2024)
- [Improbable Bigrams Expose Vulnerabilities of Incomplete Tokens in Byte-Level Tokenizers](https://mlsanity.com/paper/2410.23684/) (2024)
- [A Partition Cover Approach to Tokenization](https://mlsanity.com/paper/2501.06246/) (2025)
- [Tokenisation over Bounded Alphabets is Hard](https://mlsanity.com/paper/2511.15709/) (2025)

## Built on by (most cited first, 2 of 2)

- [Joint Optimization for Greedy Longest-match Tokenization](https://mlsanity.com/paper/2607.23362/) (2026)
- [Dynamic-Programming-Guided Hierarchical BPE and Empirical Analysis of Vocabulary Pruning](https://mlsanity.com/paper/2609.06898/) (2026)

## Abstract (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.