REVIEW
How Hard Is Tokenisation? Algorithms and Complexity Beyond NP-Hardness
Data Structures and Algorithms · Submitted 9 Nov 2026 · 15 references
Pith's verdict: Strong theoretical paper that resolves key open problems in tokenization complexity with tight inapproximability and matching algorithms.
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
Tokenization optimization is computationally near-impossible to approximate, yet not entirely hopeless.
The reading
What carries the argument
The proof of near-linear inapproximability uses a synchronizing binary code (Lemma 4.2) that ensures length-h windows in the encoded strings uniquely determine source letters, enabling a reduction from the NP-complete combinatorial rank problem. The approximation algorithm uses a grid rounding technique combined with a universal short-block vocabulary. For the savings EPTAS, the key is a small deterministic candidate pool constructed via dyadic scales and position grids that captures nearly optimal solutions. The hardness of unary merge models relies on an L-reduction from cubic vertex cover (for bottom-up) and from maximum k-vertex coverage (for optimal pair encoding), using intricate alignment and residue arguments.
Extended reading notes
Core claim
The central discovery is that binary direct token-count minimization cannot be efficiently approximated within any subpolynomial factor ($M^{{1-ε}}$) unless P=NP, even on restricted instances. This is paired with a deterministic algorithm that achieves an O(M/log M) approximation, showing that the problem is not entirely inapproximable. For compression savings, the authors give an EPTAS for fixed alphabets. They also resolve two open problems: unary bottom-up tokenization is APX-hard, and unary optimal pair encoding is strongly NP-complete.
Load-bearing premise
The hardness results assume P ≠ NP, which is standard but unproven; the derandomization of the synchronizing code relies on exact computation of conditional probabilities for events with dyadic rational probabilities, which is feasible in polynomial time.
Editorial extensions
If this is right
- No constant-factor approximation algorithm exists for binary DIRECT token-count minimization under standard complexity assumptions.
- The O(M/log M) algorithm provides a concrete practical upper bound, and budget-dependent refinements improve the ratio for small vocabularies.
- Fixed-alphabet compression savings can be approximated arbitrarily well via an EPTAS, contrasting with the inapproximability of token count.
- Unary bottom-up tokenization and unary optimal pair encoding are both computationally hard, implying that exact solutions for merge-based tokenization are intractable.
- The subexponential exact algorithm shows that the problem is not fixed-parameter tractable in K alone, but suggests tractability in parameters like cross-input sharing width.
Reading between the lines
- The stark contrast between the inapproximability of token count and the approximability of savings suggests that practical tokenization systems that minimize token count may be fundamentally heuristic, while those maximizing savings may have better worst-case guarantees.
- The synchronizing code construction may find independent use in other string problems requiring unambiguous encoding of source letters with limited window overlap.
- The EPTAS for fixed alphabets suggests that real-world applications with small alphabets (e.g., DNA) could have near-optimal solutions for compression savings.
- The open problem of fixed-parameter tractability in K alone remains; the subexponential algorithm uses parameters beyond K, hinting that more refined parameterizations may yield FPT algorithms.
Original 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.
Figures
Figures reproduced from arXiv:2611.12348 by the authors.
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.