The Computational Complexity of Optimal Tokenization

This direction is split into other directions: fixed-alphabet complexity. Its last version stays readable and citable here.

Version 1 of 110 papers42 conceptsfrozen 2026-10-04

Modern Large Language Models (LLMs) do not "read" text character by character. Instead, they process "tokens"—subword units like "ing," "the," or "trans." For years, the NLP community has relied on Byte-Pair Encoding (BPE) and other greedy heuristics to decide which strings of characters should become tokens. While these methods work well, they are essentially educated guesses.

Recent research has finally begun to explain why we rely on these heuristics: finding the mathematically "perfect" tokenizer is a computationally intractable problem.

The Myth of the Perfect Tokenizer

The goal of a tokenizer is usually framed as a compression problem: given a fixed vocabulary size (e.g., 50,000 tokens), how can we represent a massive dataset using the fewest total tokens? Intuitively, shorter sequences should be easier for a model to learn.

However, Gregor Bachmann, Tiago Pimentel, and Philip Whittington proved in Tokenisation is NP-Complete that finding this optimal vocabulary is NP-complete. By reducing the Maximum 2-Satisfiability (Max-2-SAT) problem to a string compression task, they demonstrated that an algorithm capable of finding the absolute best tokenizer would also be able to solve some of the hardest problems in computer science.

This result provides a rigorous theoretical justification for the industry’s reliance on greedy algorithms. We use BPE not because it is optimal, but because the optimal solution is unreachable for large-scale data.

Hardness Beyond Language

One might assume that the difficulty of tokenization stems from the complexity of human language—its nuances, grammar, and vast character sets. But research by Violeta Kastreva and colleagues in Tokenisation over Bounded Alphabets is Hard shows that the problem is more fundamental.

They proved that tokenization remains NP-complete even for the simplest possible alphabets, such as binary (0s and 1s) or even unary (a single repeated character). Furthermore, the problem is APX-hard, meaning it is mathematically impossible to even approximate the optimal solution within an arbitrary distance using an efficient algorithm. This suggests that the "hardness" is baked into the combinatorial logic of partitioning strings, regardless of whether the text is Shakespeare or a sequence of bits.

Reframing Tokenization as Partition Cover

To move beyond simple heuristics, researchers are reframing tokenization using classical optimization theory. In A Partition Cover Approach to Tokenization, Jia Peng Lim and Shawn Tan treat the problem as a "partition cover" task—a variation of the weighted maximum coverage problem.

By viewing tokenization through this lens, they developed GreedTok, an algorithm that applies combinatorial optimization to select a vocabulary. This approach allows researchers to provide formal approximation guarantees—mathematical bounds on how far a heuristic is from the theoretical optimum—which were previously missing from methods like BPE. As Vilém Zouhar and Clara Meister argue in A Formal Perspective on Byte-Pair Encoding, moving from "clever heuristics" to "rigorous mathematical tools" is essential for understanding the efficiency gap in modern LLMs.

Is Shorter Actually Better?

While much of this theoretical work focuses on achieving maximum compression, some researchers question if compression should be the primary goal at all. Craig W. Schmidt and Varshini Reddy introduced PATHPIECE in Tokenization Is More Than Compression to test this.

PATHPIECE achieves the theoretical maximum compression for a given vocabulary, yet the authors found that "shorter is better" is often a myth. Their results suggest that while the computational difficulty of tokenization is tied to compression, the performance of a language model is driven more by how the vocabulary is initialized and the rules used to pre-tokenize text.

Why This Matters

Understanding that tokenization is NP-complete changes the research trajectory of the field. Instead of searching for a "perfect" algorithm that doesn't exist, the focus is shifting toward:

  1. Approximation Guarantees: Developing algorithms like GreedTok that have provable bounds on their performance.
  2. Alternative Constraints: Exploring how other factors, like entropy constraints in decoding (as seen in Top-H Decoding by Erfan Baghaei Potraghloo), interact with the inherent hardness of token selection.
  3. Heuristic Refinement: Using the theoretical limits established by Philip Whittington to understand where current methods like BPE fail and how they can be incrementally improved.

By formalizing the "dark art" of tokenization, these researchers are turning a critical preprocessing step into a rigorous branch of computational linguistics.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_the_computational_complexity_of_optimal__d1e0aa0f,
  title = {The Computational Complexity of Optimal Tokenization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-computational-complexity-of-optimal-tokenization/rdr_d1e0aa0f55bf4a7aa141cc5d3fa98bef},
  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_the_computational_complexity_of_optimal__d1e0aa0f_v1,
  title = {The Computational Complexity of Optimal Tokenization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-computational-complexity-of-optimal-tokenization/rdr_d1e0aa0f55bf4a7aa141cc5d3fa98bef/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}