# Tokenisation over Bounded Alphabets is Hard

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 25 references that are in the map.
- First posted on arXiv 19 Nov 2025.

## Builds on (most cited first, 10 of 10)

- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates](https://mlsanity.com/paper/1804.10959/) (2018)
- [How Good is Your Tokenizer? On the Monolingual Performance of Multilingual Language Models](https://mlsanity.com/paper/2012.15613/) (2020)
- [Tokenizer Choice For LLM Training: Negligible or Crucial?](https://mlsanity.com/paper/2310.08754/) (2023)
- [Unpacking Tokenization: Evaluating Text Compression and its Correlation with Model Performance](https://mlsanity.com/paper/2403.06265/) (2024)
- [A Formal Perspective on Byte-Pair Encoding](https://mlsanity.com/paper/2306.16837/) (2023)
- [Greed is All You Need: An Evaluation of Tokenizer Inference Methods](https://mlsanity.com/paper/2403.01289/) (2024)
- [Theoretical Analysis of Byte-Pair Encoding](https://mlsanity.com/paper/2411.08671/) (2024)
- [Tokenisation is NP-Complete](https://mlsanity.com/paper/2412.15210/) (2024)
- [A Partition Cover Approach to Tokenization](https://mlsanity.com/paper/2501.06246/) (2025)

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

- [Tokenisation via Convex Relaxations](https://mlsanity.com/paper/2605.22821/) (2026)
- [Tokenization with Split Trees](https://mlsanity.com/paper/2605.22705/) (2026)
- [Joint Optimization for Greedy Longest-match Tokenization](https://mlsanity.com/paper/2607.23362/) (2026)
- [LangMAP: A Language-Adaptive Approach to Tokenization](https://mlsanity.com/paper/2606.23566/) (2026)
- [Objective vs. Search: Decomposing What Makes a Good Tokeniser](https://mlsanity.com/paper/2609.19145/) (2026)

## Abstract (arXiv)

Recent works have shown that tokenisation is NP-complete. However, these works assume tokenisation is applied to inputs with unboundedly large alphabets -- an unrealistic assumption, given that in practice tokenisers operate over fixed-size alphabets, such as bytes or Unicode-characters. We close this gap by analysing tokenisation over bounded alphabets, considering two natural variants: bottomup tokenisation and direct tokenisation, where we must, respectively, select a sequence of merge operations or a vocabulary whose application optimally compresses a dataset. We prove that even with binary alphabets, both variants are not only NP-complete, but also APX-hard and thus admit no polynomial-time approximation scheme (unless P=NP). We further show that direct tokenisation remains NP-complete even when applied to unary alphabets. These results establish that the computational intractability of tokenisation is not an artifact of large alphabets or complex constructions, but a fundamental barrier. Overall, our results explain why current practical algorithms such as BPE and UnigramLM are heuristic, and point toward approximation algorithms being an important path going forward for tokenisation research.