Pair-Merge Tokenisation Is Hard to Approximate on Binary Strings and Strongly NP-Hard on Unary Datasets
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 merges that leave a string of length almost as short as possible; doing nothing is already within a factor . We prove that, unless P = NP, no polynomial-time algorithm comes within a factor , for some constant , already for one binary string and for BPE-style merges that replace every occurrence. The key idea is that merges form a grammar with 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 , and no Karp reduction can prove hardness beyond order unless coNP 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
| name here | Kastreva et al. | merges act on | output | practical analogue |
|---|---|---|---|---|
| full merges (OMS) | bottom-up | all occurrences, in order | token string | BPE |
| partial merges (OPE) | – | chosen occurrences | token string | choose where merges apply |
| OPE-seg | “OPE” | (define a vocabulary) | optimal segmentation | BPE vocab., best segmentation |
| direct (not covered) | direct | (any tokens) | optimal segmentation | Unigram/WordPiece-like |
| symbol | meaning |
|---|---|
| , | length of the input string (or total length of a dataset); merge budget |
| , | dataset (multiset of strings); approximation ratio |
| minimum length after full / partial merges | |
| , | smallest number of binary rules deriving / all words of |
| string derived by a nonterminal or token | |
| , , | graph; its vertex-cover number; threshold of the source instance |
| last rule splits as | witness (length or ) | vertex it names |
| after | sequence (cover ) |
|---|---|
| start | \#\,x_{1}\;\{1}\hskip 9.24994pt#,x{2};${2}\hskip 9.24994ptx{1},#;${3}\hskip 9.24994ptx{2},#;${4}\hskip 9.24994pt#,x{1},#,x_{2},#;$_{5}$ |
| 1: | \mathbf{A_{1}}\;\{1}\hskip 9.24994pt#,x{2};${2}\hskip 9.24994ptx{1},#;${3}\hskip 9.24994ptx{2},#;${4}\hskip 9.24994pt\mathbf{A{1}},#,x_{2},#;$_{5}$ |
| 2: | A_{1}\;\{1}\hskip 9.24994pt#,x{2};${2}\hskip 9.24994ptx{1},#;${3}\hskip 9.24994ptx{2},#;${4}\hskip 9.24994pt\mathbf{C{1}},x_{2},#;$_{5}$ |
| 3: , | A_{1}\;\{1}\hskip 9.24994pt#,x{2};${2}\hskip 9.24994pt\mathbf{B{1}};${3}\hskip 9.24994pt\mathbf{B{2}};${4}\hskip 9.24994ptC{1},\mathbf{B_{2}};$_{5}$ |
| 4: | A_{1}\;\{1}\hskip 9.24994pt\mathbf{A{2}};${2}\hskip 9.24994ptB{1};${3}\hskip 9.24994ptB{2};${4}\hskip 9.24994ptC{1},B_{2};$_{5}$ |
| 5: | A_{1}\;\{1}\hskip 9.24994ptA{2};${2}\hskip 9.24994ptB{1};${3}\hskip 9.24994ptB{2};${4}\hskip 9.24994pt\mathbf{E{12}};$_{5}$ |
| merge | kind | string | head | tail |
|---|---|---|---|---|
| start | – | |||
| doubling | ||||
| doubling | ||||
| doubling | ||||
| non-doubling |