Tokenisation is NP-Complete
Philip Whittington, Gregor Bachmann, Tiago Pimentel · 2024
Read Tokenisation is NP-Complete by Philip Whittington, Gregor Bachmann, Tiago Pimentel (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-15210.txt.
Introduction
Whittington, Bachmann, and Pimentel settle a basic question about tokenisation, the step that splits text into the symbols a language model works with. They ask how hard it is, in the formal sense, to compress a data set down to at most a given number of symbols. Two variants are studied: choosing a vocabulary directly, and choosing a sequence of merge steps, as bottom-up tokenisers do. The authors prove that both variants are NP-complete, so no efficient general algorithm for optimal tokenisation should be expected.
Catalog record
| CREATOR | Philip Whittington, Gregor Bachmann, Tiago Pimentel |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 150 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-15210
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Tokenisation is NP-Complete Philip Whittington, Gregor Bachmann, Tiago Pimentel Abstract In this work, we prove the NP-completeness of two variants of tokenisation, defined as the problem of compressing a dataset to at most δ {\color[rgb]{0,0,0}\delta} symbols by either finding a vocabulary directly ( direct tokenisation), or selecting a sequence of merge operations ( bottom-up tokenisation). 1 Introduction Tokenisation is at the heart of natural language processing (NLP) being the first step required to use a language model (LM). Given a string of characters {\color[rgb]{0,0.88,0}\mathbf{{\color[rgb]{0,0.88,0}c}}} , a tokeniser converts it into a string of subwords {\color[rgb]{0.75,0,0.25}\mathbf{{\color[rgb]{0.75,0,0.25}s}}} . Language models are then trained to estimate distributions over subword strings—never seeing the original character strings. Despite its prominent role, however, much remains unknown about tokenisation. We still do not know, for instance, what makes a good tokeniser ( Gowda and May 2020 ; Cognetta et al. 2024 ) : which characteristics should its produced subwords {\color[rgb]{0.75,0,0.25}\mathbf{{\color[rgb]{0.75,0,0.25}s}}} have to be a good starting point for language modelling? If we knew this, then we could define an objective function which we could evaluate tokenisers with. Another open question is how to—given such an objective function—efficiently find a tokeniser which maximises it. Byte pair encoding ( Gage 1994 ; Sennrich et al. 2016 , BPE;) , for instance, is a greedy solution to find a tokeniser which maximises a text’s compression. UnigramLM ( Kudo 2018 ) is a heuristic method to find a tokeniser that maximises its tokenised text’s unigram log-probability. Both these methods, however, are approximate: they do not necessarily find an optimal tokeniser according to their objective function. This raises the question of whether finding such optimal tokenisers efficiently is even possible. In this paper, we answer this question (at least partially), proving the NP-completeness of several variants of this tokenisation problem. Specifically, we focus on finding tokenisers that maximise the compression of a text. 1 1 1 The compression achieved by a tokeniser correlates with downstream language modelling performance ( Gallé 2019 ; Zouhar et al. 2023a ) and computational efficiency. Given this objective, we then define the tokenisation problem as the task of finding a tokeniser which compresses a dataset to at most {\color[rgb]{0,0,0}\delta} symbols. Notably, prior work imposes different constraints on how tokenisers are defined; here we consider two variants. In direct tokenisation , the desired compression must be reached by choosing a vocabulary (i.e., a set of subwords) which is directly used to represent the text. In bottom-up tokenisation , the desired compression must be reached by finding a sequence of merge operations instead, which we apply to the input text. We prove the NP-hardness of both of these tokenisation problems (as well as of some variants thereof) by reducing from the max 2-satisfiability ( max-2-SAT ) problem. 2 2 2 Concurrent work by Kozma and Voderholzer 2024 also proves the NP-completeness of bottom-up tokenisation. In fact, they prove its APX-hardness. Practically speaking, our results imply that we are unlikely to find an efficient algorithm for the problem of finding optimal tokenisers, and that we should focus on approximate algorithms (such as BPE or UnigramLM) instead. 2 How to Choose a Tokeniser? In theory, a researcher’s choice of tokeniser should not influence their language model’s quality. This is because we can extract word-level ( Pimentel and Meister 2024 ; Oh and Schuler 2024 ) or character-level ( Phan et al. 2024 ; Giulianelli et al. 2024 ) distributions from any subword-level language model. Thus, regardless of which tokeniser is used, a sufficiently expressive language model should be able to represent the exact distributions over characters or words that we are interested in. In practice, however, a bad choice of tokeniser can have undesirable effects on downstream applications. For instance, performing standard arithmetic tasks (e.g., 317+421 ) can be difficult even for large models ( Nogueira et al. 2021 ; Muffo et al. 2022 ) due to the arbitrary splitting of numbers into subwords. Indeed, simple changes in how numbers are tokenised can improve performance in such tasks ( Singh and Strouse 2024 ) . Similar issues arise when prompting LMs to count letters in words, where even advanced models such as GPT-4 infamously cannot correctly count the number of occurrences of the letter r in the word strawberry . This raises the question of how to select a good tokeniser. Ideally, we would choose the tokeniser which maximises downstream language modelling performance. Unfortunately, we do not know how to measure such performance without fully training a model, making its direct maximisation computationally infeasible. Rather, we thus optimise proxy objectives—assumed to correlate with downstream performance. Among these are unigram log-probability ( Kudo 2018 ) , Rényi efficiency ( Zouhar et al. 2023a ) , and compression ( Gallé 2019 ) . We focus on compression in this paper. Denoting our tokenisation’s objective function as {\color[rgb]{0,0.44,0.57}\mathfrak{G}} , we write this objective as: {\color[rgb]{0,0.44,0.57}\mathfrak{G}}({\color[rgb]{0.75,0,0.25}\mathbf{{\color[rgb]{0.75,0,0.25}s}}})=-|{\color[rgb]{0.75,0,0.25}\mathbf{{\color[rgb]{0.75,0,0.25}s}}}| . Improved compression leads to: (i) more efficient training and inference, due to shortened inputs; 3 3 3 Recent work tries to improve the computational efficiency of byte-level models ( Yu et al. 2023 ; Pagnoni et al. 2024 ) . (ii) improved downstream performance, at least to a certain extent ( Gallé 2019 ; Rust et al. 2021 ; Zouhar et al. 2023a ; Goldman et al. 2024 ) ; 4 4 4 Although, see also Ali et al. 2024 , who argue that compression might be a necessary but not sufficient condition for good downstream performance, and Schmidt et al. 2024 , who argue that compression and downstream performance have a more complex relationship than prior work suggests. and (iii) fairer multilingual treatment, given models’ limited context lengths and the per-token costs to use proprietary models ( Petrov et al. 2023 ; Ahia et al. 2023 ) . Our Notation’s Colour-coding • Green for raw data (i.e., characters {\color[rgb]{0,0.88,0}\mathbf{{\color[rgb]{0,0.88,0}c}}}\in{\color[rgb]{0,0.88,0}\Sigma}^{*} ); • Purple for tokeniser-specific data (i.e., subwords {\color[rgb]{0.75,0,0.25}\mathbf{{\color[rgb]{0.75,0,0.25}s}}}\!\in\!{\color[rgb]{0.75,0,0.25}\mathcal{S}}^{*} and merges {\color[rgb]{0.75,0,0.25}\mathbf{m}}\!\in\!{\color[rgb]{0.75,0,0.25}\mathcal{M}}^{*} ); • Blue for functions (e.g., {\color[rgb]{0,0.44,0.57}\mathtt{tok}} ). 3 Defining a Tokeniser A tokeniser can be defined as a 3-tuple \langle{\color[rgb]{0.75,0,0.25}\mathcal{S}},{\color[rgb]{0,0.44,0.57}\mathtt{tok}},{\color[rgb]{0,0.44,0.57}\mathtt{detok}}\rangle , composed of a vocabulary, a tokenisation and a detokenisation function. Before defining these terms, however, we require some notation. Let {\color[rgb]{0,0.88,0}\mathbf{{\color[rgb]{0,0.88,0}c}}}={\color[rgb]{0,0.88,0}c}_{1}{\color[rgb]{0,0.88,0}c}_{2}\cdots{\color[rgb]{0,0.88,0}c}_{|{\color[rgb]{0,0.88,0}\mathbf{{\color[rgb]{0,0.88,0}c}}}|}\in{\color[rgb]{0,0.88,0}\Sigma}^{*} be a character-string , i.e., a sequence of characters {\color[rgb]{0,0.88,0}c} from alphabet {\color[rgb]{0,0.88,0}\Sigma} . Further, let {\color[rgb]{0,0,0}\mathcal{D}}\!=\!\{{\color[rgb]{0,0.88,0}\mathbf{{\color[rgb]{0,0.88,0}c}}}_{n}\}_{n=1}^{N} be a dataset of character-strings. 5 5 5 We note that we use set notation here, but our datasets are actually multisets—datasets can include the same string {\color[rgb]{0,0.88,0}\mathbf{{\color[rgb]{0,0.88,0}c}}} multiple times. We show that tokenisation is still NP-complete for datasets with no repetitions in section 6.3 . Further, we impose no constraint on the kind of string present in these datasets: each {\color[rgb]{0,0.88,0}\mathbf{{\color[rgb]{0,0.88,0}c}}}_{n} can be either a raw or pre-tokenised character-string (i.e., either a full document or a whitespace word). A subword {\color[rgb]{0.75,0,0.25}s}\!\in\!{\color[rgb]{0.75,0,0.25}\mathcal{S}} represents a non-empty character-string {\color[rgb]{0,0.88,0}\mathbf{{\color[rgb]{0,0.88,0}c}}} . (Sequence {\color[rgb]{0,0.88,0}\mathbf{{\color[rgb]{0,0.88,0}c}}} can have length one.) Finally, let {\color[rgb]{0.75,0,0.25}\mathbf{{\color[rgb]{0.75,0,0.25}s}}}={\color[rgb]{0.75,0,0.25}\langle{\color[rgb]{0.75,0,0.25}s}_{1},{\color[rgb]{0.75,0,0.25}s}_{2},\cdots,{\color[rgb]{0.75,0,0.25}s}_{|{\color[rgb]{0.75,0,0.25}\mathbf{{\color[rgb]{0.75,0,0.25}s}}}|}\rangle}\in{\color[rgb]{0.75,0,0.25}\mathcal{S}}^{*} be a subword-string . Just like a single subword, a subword-string {\color[rgb]{0.75,0,0.25}\mathbf{{\color[rgb]{0.75,0,0.25}s}}}\in{\color[rgb]{0.75,0,0.25}\mathcal{S}}^{*} represents a character-string via the concatenation of its subwords’ characters: \displaystyle{\color[rgb]{0,0.44,0.57}\mathtt{concat}}({\color[rgb]{0.75,0,0.25}\mathbf{{\color[rgb]{0.75,0,0.25}s}}})={\color[rgb]{0.75,0,0.25}s}_{1}\circ{\color[rgb]{0.75,0,0.25}s}_{2}\circ...\circ{\color[rgb]{0.75,0,0.25}s}_{|{\color[rgb]{0.75,0,0.25}\mathbf{{\color[rgb]{0.75,0,0.25}s}}}|} (1) and we say that a pair of character and subword strings are equivalent if: \displaystyle{\color[rgb]{0,0.88,0}\mathbf{{\color[rgb]{0,0.88,0}c}}}\,{\color[rgb]{0,0.44,0.57}\stackrel{{\scriptstyle{\circ}}}{{=}}}\,{\color[rgb]{0.75,0,0.25}\mathbf{{\color[rgb]{0.75,0,0.25}s}}}\iff{\color[rgb]{0,0.88,0}\mathbf{{\color[rgb]{0,0.88,0}c}}}={\color[rgb]{0,0.44,0.57}\mathtt{concat}}({\color[rgb]{0.75,0,0.25}\mathbf{{\color[rgb]{0.75,0,0.25}s}}}) (2) Given the notation above, we can now define the items in tuple \langle{\color[rgb]{0.75,0,0.25}\mathcal{S}},{\color[rgb]{0,0.44,0.57}\mathtt{tok}},{\color[rgb]{0,0.44,0.57}\mathtt{detok}}\rangle . A tokeniser’s vocabulary is a