How Hard Is Tokenisation? Algorithms and Complexity Beyond NP-Hardness
En palabras de los autores
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 approximation, for fixed , unless , even on distinct equal-length strings with . Here is the total input length and is the number of input strings. We complement this lower bound with a deterministic polynomial-time 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 time, where is the total length of the distinct input strings and 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.
Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.