The Computational Complexity of Optimal Tokenization

21 concepts5 papers1 proposal

Modern language models do not process raw text; they process tokens. The standard way to create these tokens—algorithms like Byte Pair Encoding (BPE) or UnigramLM—relies on greedy heuristics. While these methods work well in practice, a growing body of research suggests that the quest for a "perfect" tokenizer is not just difficult, but mathematically intractable.

The Tokenization Optimization Problem

At its core, tokenization is a compression problem. Given a large corpus of text and a fixed budget for a vocabulary size $V$, we want to find a set of subword units that represents the corpus using the fewest total tokens.

As Whittington et al. argue, this is distinct from standard dictionary compression. In typical compression, you try to minimize the combined size of the dictionary and the data. In NLP, the dictionary size is a strict constraint (e.g., exactly 50,000 tokens), and we only care about minimizing the resulting sequence length. This specific constraint structure transforms a common engineering task into a fundamental computational hurdle.

Why Global Optimality is Out of Reach

If we could find the mathematically optimal vocabulary, we might significantly improve model efficiency and reasoning. However, Whittington et al. prove that finding this optimal tokenizer is NP-complete. This means that as the size of our data and vocabulary grows, the time required to find the absolute best solution increases exponentially.

This intractability is further clarified by Lim et al., who reframe tokenization as a partition cover problem. In this view, we are trying to select a subset of all possible substrings to "cover" the text. The authors prove this framing is NP-hard, explaining why iterative merge heuristics like BPE often fall into local optima and fail to reach the minimum possible token count.

Hardness Across All Scales

One might wonder if this complexity is a byproduct of the massive, diverse alphabets used in human language (like Unicode). Perhaps the problem becomes trivial if we restrict ourselves to a simple binary alphabet?

Kastreva et al. demonstrate that this is not the case. They prove that tokenization remains NP-complete even for bounded alphabets, including binary (0s and 1s) and even unary strings. Furthermore, they show the problem is APX-hard, meaning we cannot even design an efficient algorithm that is guaranteed to get "close enough" to the global optimum for every case. The difficulty is an inherent property of the string partitioning task itself, not the complexity of the characters involved.

Complexity at Inference Time

The challenge isn't limited to building the vocabulary; it also extends to how we use it. While we usually pick a single "canonical" tokenization for a string, there are exponentially many ways to break a sentence into subwords.

Zhang et al. show that identifying the most probable tokenization for an autoregressive model is NP-complete. Even more daunting, calculating the exact marginal probability across all possible tokenizations is #P-hard. This suggests that our models are currently ignoring a vast "tokenization space" of alternative signals because the cost of exploring that space is computationally prohibitive.

Living with Intractability

Because the global optimum is unreachable, research has shifted toward better approximation strategies and constrained decoding:

  • Improved Heuristics: Lim et al. introduced GreedTok, which applies approximation guarantees from weighted maximum coverage theory to outperform BPE and Unigram in 1B-parameter models.
  • Constrained Sampling: In the context of generation, Potraghloo et al. address the NP-hard problem of selecting token subsets under entropy constraints. Their Top-H decoding uses greedy heuristics to balance creativity and coherence, showing that even when we cannot reach the theoretical optimum, mathematically grounded heuristics can yield significant gains in creative writing and logical consistency.

Ultimately, these proofs of NP-completeness validate the industry's reliance on greedy algorithms. By establishing that perfect tokenization is a "hard" problem, the authors—including Whittington et al. and Kastreva et al.—provide the theoretical justification for moving away from a search for perfection and toward more sophisticated, principled approximations.

Key Foundational Work

Tokenisation is NP-Complete (2025) — contributed 7 concept elements to this direction.
A Partition Cover Approach to Tokenization (2025) — contributed 5 concept elements to this direction.
Where is the signal in tokenization space? (2024) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_fixed_alphabet_complexity_1eadf696,
  title = {fixed-alphabet complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fixed-alphabet-complexity/rdr_1eadf696ab7344c783c054b891338144},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_fixed_alphabet_complexity_1eadf696_v1,
  title = {fixed-alphabet complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fixed-alphabet-complexity/rdr_1eadf696ab7344c783c054b891338144/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake