Binary tokenization is hard but allows approximate efficient solutions
Tokenization: Hardness and Bicriteria Approximation Algorithms
Data Structures and AlgorithmsArtificial IntelligenceComputational Complexity
Summary
This paper looks at how to efficiently break down binary data sequences into pieces from a limited dictionary to minimize the total number of pieces needed. The authors prove that finding the best way to do this is very hard, to the point that no fast method can guarantee a close-to-best solution unless a major unsolved math problem is solved. However, they also present new algorithms that relax some limits and provide solutions that come close to the best possible, within factors related to document size and dictionary budget. They extend their methods to cases where the total size of pieces is limited too.
What this means in practice
- •For data compression engineers: Determine theoretical limits on token dictionary design that guide compression algorithm trade-offs for binary data.
- •For software developers using tokenization: Use bicriteria approximation algorithms to build tokenizers that efficiently balance vocabulary size and token count.
A theory result. No direct application yet.
Authors
Atieh Bastan, Xiaoling He, A. Pavan, N. V. Vinodchandran
Abstract
We study Binary Tokenization: given a corpus of binary strings over $\{0,1\}$ and a vocabulary budget $K$, select at most $K$ substrings (called vocabulary) to minimize the total number of tokens needed to represent the corpus. The primitive symbols $0$ and $1$ are always available, and each document must be segmented separately. Letting $n$ denote the total corpus length and $M$ for the maximum document length, we prove that, for every fixed $\varepsilon\in(0,1)$, Binary Tokenization problem does not have polynomial-time $n^{1-\varepsilon}$-approximation algorithms unless $\mathsf{P}=\mathsf{NP}$. To complement the hardness result, we give a polynomial-time $(γ,γ)$-bicriteria algorithm, with $γ= \sqrt{M}\log n$: The algorithm outputs a vocabulary of size at most $γK$ with number of tokens at most $γ{\rm OPT}_K$, where ${\rm OPT}_K$ is the optimal number of tokens under the original budget $K$. We also study a storage-budget variant, in which the sum of the selected substrings' lengths is bounded by $B$. For $2\le B<n$, we obtain an $(O(\log n\log B),O(\log n\log B))$-bicriteria approximation algorithm.