Complexity limits and algorithms for efficient string tokenisation
How Hard Is Tokenisation? Algorithms and Complexity Beyond NP-Hardness
Data Structures and Algorithms
Summary
This paper studies how hard it is to break down collections of strings into tokens efficiently while keeping the total number of tokens low. The authors prove that finding a near-perfect solution in polynomial time is extremely unlikely unless P equals NP, meaning it is very hard in a theoretical sense. They also provide new algorithms that offer approximate and exact solutions in different scenarios. Their work clarifies how tough tokenisation problems can be under various models and gives ways to handle them efficiently when exact solutions are impractical.
What this means in practice
- •For data compression engineers: Optimize tokenisation strategies within fixed vocabulary limits to improve compression efficiency based on the new approximation algorithms.
- •For natural language processing developers: Design tokenisation components aware of fundamental complexity limits to balance speed and solution quality in text processing pipelines.
A theory result. No direct application yet.
Authors
Andrei Robert Ion, Rares Mateiu, Adrian Miclaus, Alexandru Popa
Abstract
Given a collection of strings and a vocabulary budget, how well can we minimize its total token count, and how does the answer change with the tokenisation model? For binary direct tokenisation, previous work proved APX-hardness but left constant-factor approximability unresolved \citep{kastreva2026}. We rule out every polynomial-time $M^{1-\varepsilon}$ approximation, for fixed $\varepsilon>0$, unless $\mathrm{P}=\mathrm{NP}$, even on distinct equal-length strings with $K=m-1$. Here $M$ is the total input length and $m$ is the number of input strings. We complement this lower bound with a deterministic polynomial-time $O(M/\log M)$ approximation algorithm and stronger bounds for selected vocabulary budgets. For the different objective of maximizing compression savings, GreedTok was shown to attain a constant fraction of the optimum on unrestricted alphabets \citep{baliga2026}; we establish a deterministic EPTAS for direct savings on every fixed alphabet and analyze greedy selection by true marginal gains. For exact optimization, we give a binary direct algorithm running in $2^{O(n\log\log n/\log n)}\poly(I)$ time, where $n$ is the total length of the distinct input strings and $I$ is the input encoding length. Finally, we resolve two unary merge-model hardness questions left by the bounded-alphabet study \citep{kastreva2026}: standard unary bottom-up tokenisation is APX-hard, and unary optimal pair encoding is strongly NP-complete, strengthening the previously known weak hardness.