# Tokenisation is NP-Complete

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 39 references that are in the map.
- First posted on arXiv 19 Dec 2024.

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

- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [Pythia: A Suite for Analyzing Large Language Models Across Training and Scaling](https://mlsanity.com/paper/2304.01373/) (2023)
- [Language Model Tokenizers Introduce Unfairness Between Languages](https://mlsanity.com/paper/2305.15425/) (2023)
- [Do All Languages Cost the Same? Tokenization in the Era of Commercial Language Models](https://mlsanity.com/paper/2305.13707/) (2023)
- [MEGABYTE: Predicting Million-byte Sequences with Multiscale Transformers](https://mlsanity.com/paper/2305.07185/) (2023)
- [Byte Latent Transformer: Patches Scale Better Than Tokens](https://mlsanity.com/paper/2412.09871/) (2024)
- [Investigating the Limitations of Transformers with Simple Arithmetic Tasks](https://mlsanity.com/paper/2102.13019/) (2021)
- [Scaling Laws with Vocabulary: Larger Models Deserve Larger Vocabularies](https://mlsanity.com/paper/2407.13623/) (2024)
- [Tokenization counts: the impact of tokenization on arithmetic in frontier LLMs](https://mlsanity.com/paper/2402.14903/) (2024)
- [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)
- [How to Compute the Probability of a Word](https://mlsanity.com/paper/2406.14561/) (2024)
- [Where is the signal in tokenization space?](https://mlsanity.com/paper/2408.08541/) (2024)
- [Understanding and Mitigating Tokenization Bias in Language Models](https://mlsanity.com/paper/2406.16829/) (2024)
- [Theoretical Analysis of Byte-Pair Encoding](https://mlsanity.com/paper/2411.08671/) (2024)
- [Evaluating Transformer Language Models on Arithmetic Operations Using Number Decomposition](https://mlsanity.com/paper/2304.10977/) (2023)
- [On the Proper Treatment of Tokenization in Psycholinguistics](https://mlsanity.com/paper/2410.02691/) (2024)
- [On the Effect of (Near) Duplicate Subwords in Language Modelling](https://mlsanity.com/paper/2404.06508/) (2024)
- [At the Roots of Dictionary Compression: String Attractors](https://mlsanity.com/paper/1710.10964/) (2017)

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

- [Causal Estimation of Tokenisation Bias](https://mlsanity.com/paper/2506.03149/) (2025)
- [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)
- [Tokenisation via Convex Relaxations](https://mlsanity.com/paper/2605.22821/) (2026)
- [UNVEILING: What Makes Linguistics Olympiad Puzzles Tricky for LLMs?](https://mlsanity.com/paper/2508.11260/) (2025)
- [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)
- [Training Language Models with homotokens Leads to Delayed Overfitting](https://mlsanity.com/paper/2601.02867/) (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)

In this work, we prove the NP-completeness of two variants of tokenisation, defined as the problem of compressing a dataset to at most δ symbols by either finding a vocabulary directly (direct tokenisation), or selecting a sequence of merge operations (bottom-up tokenisation).