Papers for

software developers using tokenization

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Binary tokenization is hard but allows approximate efficient solutions

Tokenization: Hardness and Bicriteria Approximation Algorithms

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.

Wed 11 NovData Structures and AlgorithmsArtificial IntelligenceComputational Complexity
The gist
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.
Open → 2611.15074v1