cs.DSNov 10, 2026

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

Authors: Kundan Baliga, Aiden Xie, Aditya Byju

Organizations: University of Illinois Urbana-Champaign · Georgia Institute of Technology

Abstract

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.

Figures & tables

Explore similar work

Nov 11, 2026

Tokenization: Hardness and Bicriteria Approximation Algorithms

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.
Nov 5, 2026

Greedy Byte-Pair Encoding Achieves 0.391 of the Optimum, Past the One-Third Barrier for Packing-Based Analyses

Byte-Pair Encoding (BPE) builds most language-model tokenisers by repeatedly merging a most frequent adjacent pair of symbols. How much shortening can this greedy rule lose against the best kk merges? Kozma and Voderholzer proved that greedy achieves at least one third of the optimal shortening; the best known upper bound is (1−e−2)/2≈0.432(1-e^{-2})/2\approx 0.432. We show that one third is a barrier for packing-based analyses, which see the optimum only through a pair packing, and we prove that greedy achieves at least 0.3910.391 of the optimum on every input, with any tie-breaking. The key idea is rule determinism: all copies of a rule of the optimum spell the same letters, so when one greedy replacement destroys three of the optimum's merge points, half a unit can be refunded on each side. A weaker bound, 0.3740.374, has a short proof that needs no computer; 0.3910.391 adds a certificate in exact arithmetic. We also show that the worst-case ratio is exactly 3/43/4 for two merges and at most 7/127/12 for three.
Nov 13, 2024

Theoretical Analysis of Byte-Pair Encoding

Byte-Pair Encoding (BPE) is a widely used method for subword tokenization, with origins in grammar-based text compression. It is employed in a variety of language processing tasks such as machine translation or large language model (LLM) pretraining, to create a token dictionary of a prescribed size. Most evaluations of BPE to date are empirical, and the reasons for its good practical performance are not well understood. In this paper we focus on the optimization problem underlying BPE: finding a pair encoding that achieves optimal compression utility. We show that this problem is APX-complete, indicating that it is unlikely to admit a polynomial-time approximation scheme. This answers, in a stronger form, a question recently raised by Zouhar et al. On the positive side, we show that BPE approximates the compression utility of the optimal pair encoding to a worst-case factor between 1/31/3 and (1−e−2)/2≈0.4324(1-e^{-2})/2 \approx 0.4324. Our results aim to explain the ongoing success of BPE and are, to our knowledge, the first rigorous guarantees on its compression utility that hold for all inputs.