cs.DSNov 11, 2026

Tokenization: Hardness and Bicriteria Approximation Algorithms

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

Organizations: Iowa State University. · University of Nebraska–Lincoln.

Abstract

We study Binary Tokenization: given a corpus of binary strings over {0,1}\{0,1\} and a vocabulary budget KK, select at most KK substrings (called vocabulary) to minimize the total number of tokens needed to represent the corpus. The primitive symbols 00 and 11 are always available, and each document must be segmented separately. Letting nn denote the total corpus length and MM for the maximum document length, we prove that, for every fixed ε∈(0,1)\varepsilon\in(0,1), Binary Tokenization problem does not have polynomial-time n1−εn^{1-\varepsilon}-approximation algorithms unless P=NP\mathsf{P}=\mathsf{NP}. To complement the hardness result, we give a polynomial-time (γ,γ)(γ,γ)-bicriteria algorithm, with γ=Mlog⁡nγ= \sqrt{M}\log n: The algorithm outputs a vocabulary of size at most γKγK with number of tokens at most γOPTKγ{\rm OPT}_K, where OPTK{\rm OPT}_K is the optimal number of tokens under the original budget KK. We also study a storage-budget variant, in which the sum of the selected substrings' lengths is bounded by BB. For 2≤B<n2\le B<n, we obtain an (O(log⁡nlog⁡B),O(log⁡nlog⁡B))(O(\log n\log B),O(\log n\log B))-bicriteria approximation algorithm.

Explore similar work

CardsList
  1. Pair-Merge Tokenisation Is Hard to Approximate on Binary Strings and Strongly NP-Hard on Unary Datasets

    Nov 10, 2026Kundan Baliga, Aiden Xie, Aditya ByjuTokenizationByte-Pair Encoding

  2. Tokenisation via Convex Relaxations

    May 21, 2026Jan Tempus, Philip Whittington, Craig W. Schmidt +2Token EfficiencyLinear Programming

  3. Tokenization with Split Trees

    May 21, 2026Craig W. Schmidt, Michael Krumdick, Adam Wiemerslage +4Token EfficiencySubword Tokenization