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

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.