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

Nov 10, 2026

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

Tokenisers such as Byte-Pair Encoding (BPE) shorten text by repeatedly merging an adjacent pair of symbols into a new one; fewer tokens mean less computation. We ask whether an efficient algorithm can choose kk merges that leave a string of length nn almost as short as possible; doing nothing is already within a factor nn. We prove that, unless P = NP, no polynomial-time algorithm comes within a factor c n/log⁡nc\,n/\log n, for some constant c>0c>0, already for one binary string and for BPE-style merges that replace every occurrence. The key idea is that kk merges form a grammar with kk rules: a vertex-cover gap becomes a grammar-size gap, which we amplify with relabelled copies, encode in binary and realise with explicit merges. For merges that may skip occurrences, a simple algorithm achieves O(n/log⁡log⁡n)O(n/\log\log n), and no Karp reduction can prove hardness beyond order n/log⁡nn/\log n unless coNP ⊆\subseteq NP/poly. Over a one-letter alphabet, both tokenisation problems left open by Kastreva et al. are strongly NP-complete on datasets with repeated strings.
May 21, 2026

Tokenisation via Convex Relaxations

Tokenisation is an integral part of the current NLP pipeline. Current tokenisation algorithms such as BPE and Unigram are greedy algorithms -- they make locally optimal decisions without considering the resulting vocabulary as a whole. We instead formulate tokeniser construction as a linear program and solve it using convex optimisation tools, yielding a new algorithm we call ConvexTok. We find ConvexTok consistently improves intrinsic tokenisation metrics and the bits-per-byte (BpB) achieved by language models; it also improves downstream task performance, but less consistently. Furthermore, ConvexTok allows the user to certify how far their tokeniser is from optimal, with respect to a certain objective, via a lower bound, and we empirically find it to be within 1% of optimal at common vocabulary sizes.
May 21, 2026

Tokenization with Split Trees

We introduce Tokenization with Split Trees (ToaST), a subword tokenization method that directly optimizes compression under a new recursive inference procedure. ToaST greedily splits each pretoken into a full binary tree using precomputed byte n-gram counts, independent of any vocabulary. Given a vocabulary, inference recursively descends each split tree and emits the first in-vocabulary node reached on each path. Vocabulary selection is formulated as an Integer Program (IP) that minimizes the total token count over all split trees under this inference procedure. The Linear Programming (LP) relaxation is near-integral in practice, yielding provably near-optimal vocabularies, with training time empirically scaling quadratically in the number of split trees. On English text, ToaST reduces token counts by more than 11% compared to BPE, WordPiece, and UnigramLM at vocabulary sizes of 40,960 and above, reducing the number of inference tokens for models using this tokenizer, thus extending the effective context length. ToaST also uses common single-byte tokens less frequently than these baselines, leading to a substantial improvement in Renyi efficiency. In experiments training 1.5B parameter language models, ToaST achieves the highest CORE score, outperforming baselines by 2.6%--7.6%, with significance for two of three, and scoring best on 13 of 22 individual tasks.