mlsanityData to 14 Oct 2026

Tokenisation is NP-Complete

arXiv 2412.15210 ↗First posted 19 Dec 2024cs.DS cs.CL cs.FLcited by 10

Not on the map. Why?

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).

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

22 of 39 references.

References · 22

  1. 2023LLaMA: Open and Efficient Foundation Language Modelscited by 14,132
  2. 2023Llama 2: Open Foundation and Fine-Tuned Chat Modelscited by 13,028
  3. 2015Neural Machine Translation of Rare Words with Subword Unitscited by 2,918
  4. 2023Pythia: A Suite for Analyzing Large Language Models Across Training and Scalingcited by 1,786
  5. 2023Language Model Tokenizers Introduce Unfairness Between Languagescited by 214
  6. 2023Do All Languages Cost the Same? Tokenization in the Era of Commercial Language Modelscited by 192
  7. 2023MEGABYTE: Predicting Million-byte Sequences with Multiscale Transformerscited by 170
  8. 2024Byte Latent Transformer: Patches Scale Better Than Tokenscited by 146
  9. 2021Investigating the Limitations of Transformers with Simple Arithmetic Taskscited by 139
  10. 2024Scaling Laws with Vocabulary: Larger Models Deserve Larger Vocabulariescited by 118
  11. 2024Tokenization counts: the impact of tokenization on arithmetic in frontier LLMscited by 115
  12. 2023Tokenizer Choice For LLM Training: Negligible or Crucial?cited by 108
10 more
  1. 2024Unpacking Tokenization: Evaluating Text Compression and its Correlation with Model Performancecited by 61
  2. 2023A Formal Perspective on Byte-Pair Encodingcited by 36
  3. 2024How to Compute the Probability of a Wordcited by 36
  4. 2024Where is the signal in tokenization space?cited by 21
  5. 2024Understanding and Mitigating Tokenization Bias in Language Modelscited by 18
  6. 2024Theoretical Analysis of Byte-Pair Encodingcited by 16
  7. 2023Evaluating Transformer Language Models on Arithmetic Operations Using Number Decompositioncited by 15
  8. 2024On the Proper Treatment of Tokenization in Psycholinguisticscited by 13
  9. 2024On the Effect of (Near) Duplicate Subwords in Language Modellingcited by 5
  10. 2017At the Roots of Dictionary Compression: String Attractorscited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 4; 2026: 6.

10 papers.

  1. 2025Causal Estimation of Tokenisation Biascited by 16
  2. 2025A Partition Cover Approach to Tokenizationcited by 5
  3. 2025Tokenisation over Bounded Alphabets is Hardcited by 5
  4. 2026Tokenisation via Convex Relaxationscited by 4
  5. 2025UNVEILING: What Makes Linguistics Olympiad Puzzles Tricky for LLMs?cited by 3
  6. 2026Tokenization with Split Treescited by 2
  7. 2026Joint Optimization for Greedy Longest-match Tokenizationcited by 1
  8. 2026Training Language Models with homotokens Leads to Delayed Overfittingcited by 0
  9. 2026LangMAP: A Language-Adaptive Approach to Tokenizationcited by 0
  10. 2026Objective vs. Search: Decomposing What Makes a Good Tokenisercited by 0