# Tokenization: Hardness and Bicriteria Approximation Algorithms

DevFeed: [Tokenization: Hardness and Bicriteria Approximation Algorithms](<https://devfeed.tech/articles/tokenization-hardness-and-bicriteria-approximation-algorithms-132091.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.15074>)

Author: Atieh Bastan, Xiaoling He, A. Pavan, N. V. Vinodchandran

Published: 2026-11-13T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Artificial Intelligence](<https://devfeed.tech/sources/arxiv-artificial-intelligence.md>)

Topics: [tokenization](<https://devfeed.tech/topics/tokenization.md>), [Algorithms](<https://devfeed.tech/topics/algorithms.md>), [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>)

Tags: [algorithms](<https://devfeed.tech/tags/algorithms.md>), [approximation](<https://devfeed.tech/tags/approximation.md>), [approximation-algorithms](<https://devfeed.tech/tags/approximation-algorithms.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [cs-cc](<https://devfeed.tech/tags/cs-cc.md>), [cs-ds](<https://devfeed.tech/tags/cs-ds.md>), [tokenization](<https://devfeed.tech/tags/tokenization.md>)

## AI overview

Binary Tokenization selects up to K substrings from a corpus of binary strings to minimize the total tokens needed to segment each document; the single symbols 0 and 1 are always available. For total corpus length n and maximum document length M, the abstract proves that no polynomial-time n^(1−ε)-approximation exists for any fixed ε in (0,1), unless P=NP. It also gives a polynomial-time bicriteria algorithm with γ=√M log n: it uses at most γK vocabulary entries and at most γ times the optimum token count under budget K. In the storage-budget variant, where selected substring lengths sum to at most B, the stated bicriteria factors are both O(log n log B) for 2≤B<n.

## Source excerpt

arXiv:2611.15074v1 Announce Type: cross 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 $(\gamma,\gamma)$-bicriteria algorithm, with $\gamma = \sqrt{M}\log n$: The algorithm outputs a vocabulary of size at most $\gamma K$ with number of tokens at most $\gamma {\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