💬 NLP

Tokenisation over Bounded Alphabets is Hard

This paper proves that tokenisation over bounded alphabets, including binary and unary cases, is fundamentally NP-complete and APX-hard, establishing that its computational intractability is an inherent barrier rather than an artifact of large input alphabets and explaining the necessity of heuristic approaches in current practical algorithms.

Original authors: Violeta Kastreva, Philip Whittington, Dennis Komm, Tiago Pimentel

Published 2026-08-11

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Violeta Kastreva, Philip Whittington, Dennis Komm, Tiago Pimentel

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to send a secret message to a friend, but the only way to send it is by breaking your words into tiny, pre-approved chunks. If you send "superduper," you might have to break it into "super" and "duper" instead of the whole word, because your friend's dictionary only has those two pieces. This is the heart of tokenization, the first step in teaching computers to understand human language. Before a computer can read a sentence, it must chop it up into these manageable "tokens" (like Lego bricks). The goal is to chop the text up in a way that uses the fewest bricks possible, making the message shorter and faster to send. This is called compression. If you can compress a book into fewer bricks, the computer can read it faster and learn from it more efficiently. For years, scientists have been building clever, greedy algorithms—like a child grabbing the biggest available Lego piece they can find—to do this chopping automatically. But a big question has lingered: Is there a perfect, mathematically optimal way to chop any text, or are we stuck with "good enough" guesses?

This paper, titled "Tokenisation Over Bounded Alphabets Is Hard," dives into the deep end of that question. The authors, a team of researchers from ETH Zürich and Sofia University, set out to prove whether finding that perfect chopping method is actually a nightmare for computers, even when the rules are simple. They focus on two main ways of chopping: Direct Tokenisation, where you pick the best set of Lego bricks (a vocabulary) all at once, and Bottom-Up Tokenisation, where you start with single letters and keep gluing pairs together until you run out of glue (merges). The big twist in their story is that they test these methods not on the infinite, chaotic alphabet of all possible human sounds, but on the tiny, fixed sets we actually use in computers: binary (just 0s and 1s, like a light switch) and unary (just one single symbol, like a string of identical beads).

The paper's main finding is a resounding "No, you cannot easily find the perfect solution." The authors prove that even with the simplest possible alphabets—like a world made only of zeros and ones—finding the optimal way to compress text is NP-complete and APX-hard. In plain English, this means that no matter how much computing power you throw at the problem, there is no fast, efficient algorithm that can guarantee the best possible result. It's not just that the problem is hard; it's that it's fundamentally hard. The paper explicitly rules out the idea that the difficulty comes from the complexity of human language or huge alphabets. Instead, they show that the barrier exists even in the simplest, most restricted scenarios. Furthermore, they prove that you can't even get "close enough" to the perfect answer in a reasonable amount of time; there is no polynomial-time approximation scheme (PTAS) that can get arbitrarily close to the best solution unless a major mathematical mystery (P = NP) is solved.

The researchers also tackle the unary case, where the alphabet has only one symbol (think of a message made entirely of the letter "a"). You might think, "If I only have one letter, how hard can it be?" Surprisingly, they prove that even here, finding the optimal way to chop the text is strongly NP-complete. This is a heavy mathematical result suggesting that the difficulty isn't just a quirk of large data sets; it's baked into the very logic of trying to compress text optimally.

So, what does this mean for the future? The paper doesn't offer a new, magical algorithm to solve the problem. Instead, it explains why the tools we use today, like BPE (Byte-Pair Encoding) and UnigramLM, are forced to be heuristic—meaning they use clever shortcuts and guesses rather than calculating the perfect answer. The authors argue that because the perfect answer is computationally impossible to find quickly, researchers should stop chasing the "holy grail" of the optimal tokeniser and instead focus on building better, provably good approximation methods. The door to perfection is locked, and the key doesn't exist; the best we can do is learn to pick the best lock-pick we have.

Problem Statement
Recent theoretical work has established that finding an optimal tokeniser for a dataset is NP-complete. However, these prior results rely on the assumption that tokenisation operates over unboundedly large alphabets. In practical natural language processing, tokenisers operate over fixed-size, bounded alphabets (e.g., bytes with size 256, Unicode characters with size ~170,000, or binary/bit strings with size 2). It remains an open question whether the computational intractability of tokenisation persists when the alphabet size is bounded by a constant. This paper addresses this gap by analysing the complexity of tokenisation over bounded alphabets, specifically investigating whether optimal tokenisers can be found efficiently for binary (size 2) and unary (size 1) alphabets.

Methodology
The authors define the $n$ -ary tokenisation problem, where the input alphabet $\Sigma$ has size $n$ . They analyse two natural variants of tokenisation:

Direct Tokenisation: Finding a vocabulary $S$ of size $K$ that, when applied optimally to a dataset, minimises the total compressed length.
Bottom-up Tokenisation: Finding a sequence of $K$ merge operations that, when applied sequentially to a dataset, minimises the total compressed length.

The objective function used is compressed length (the total number of tokens after encoding), which correlates with model training and inference costs. The authors employ standard complexity-theoretic techniques to establish hardness:

NP-Hardness: Proved via polynomial-time reductions from known NP-hard problems (specifically 3-OCC-MAX2SAT and Vertex Cover) to the tokenisation decision problems.
APX-Hardness: Proved via L-reductions (approximation-preserving reductions) from APX-complete problems. This demonstrates that the problems are not in the class PTAS (Polynomial-Time Approximation Scheme), meaning they cannot be approximated arbitrarily well in polynomial time unless P = NP.
Gap Problems: The authors define gap versions of the problems to derive explicit hardness-of-approximation constants.

Key Contributions and Results

Binary Tokenisation is APX-Hard:
The paper proves that both binary direct tokenisation and binary bottom-up tokenisation are APX-hard.
- Direct Case: It is shown that binary direct tokenisation cannot be approximated in polynomial time with an approximation ratio $\rho < 1.000002$ (unless P = NP).
- Bottom-up Case: Similarly, binary bottom-up tokenisation is APX-hard with a hardness constant of $\rho < 1.0000001$ .
- These results imply that even for the simplest non-trivial alphabet (binary), finding an optimal tokeniser is computationally intractable, and no polynomial-time algorithm can guarantee an arbitrarily close approximation to the optimum.
Unary Tokenisation is Strongly NP-Complete:
The authors investigate the unary case (alphabet size 1), which is theoretically the "easiest" variant.
- They prove that unary direct tokenisation is strongly NP-complete. This is achieved via a reduction from the Vertex Cover problem. The proof establishes that the hardness is intrinsic to the problem structure and not an artifact of the input representation (string vs. string-length).
- For unary bottom-up tokenisation, the paper establishes that a variant known as Optimal Pair Encoding (OPE) tokenisation is (at least) weakly NP-complete, via a reduction from the Addition Chain problem. The complexity of standard unary bottom-up tokenisation remains an open question in this work.
Hierarchy of Hardness:
The paper establishes a clear hierarchy: if $n$ -ary tokenisation is hard, then $n'$ -ary tokenisation for all $n' > n$ is also hard. Consequently, the hardness results for binary and unary cases trivially extend to all larger bounded alphabets (including byte and Unicode alphabets).

Significance and Claims
The paper claims that these results fundamentally alter the understanding of tokenisation complexity. By proving that tokenisation remains hard even over unary and binary alphabets, the authors demonstrate that the computational intractability is not an artifact of large alphabets or complex merge operations. Instead, it is a fundamental barrier inherent to the problem of optimally compressing data via tokenisation.

These findings provide a theoretical justification for why current practical algorithms, such as Byte-Pair Encoding (BPE) and UnigramLM, rely on heuristics and greedy strategies rather than exact optimisation. The paper concludes that future research should focus on developing provably good approximation algorithms or relaxing the problem constraints, as finding exact optimal tokenisers is likely impossible for any non-trivial dataset size.

More like this