How to Write your Paper's Intro?

Large language models (LMs) are often pretrained with a single pass on web-scale datasets (Raffel et al., 2020; Gao et al., 2020; Penedo et al., 2023, inter alia). Given the colossal size of these training sets, one may expect each individual instance to have little impact on the final model. Yet, LMs can still reproduce entire sequences from their training set verbatim (Carlini et al., 2021), suggesting that models can store, or memorise, precise knowledge about individual training instances. In the era of large LMs, measuring memorisation is crucial for NLP practitioners; it has implications for copyright and data protection (Hu et al., 2022; Vyas et al., 2023; Lee et al., 2023), for how models encode factual information (Cao et al., 2022; Tirumala et al., 2022), and for understanding their training dynamics (Arpit et al., 2017; Chang and Bergen, 2024).

Tokenisation is at the heart of natural language processing (NLP) being the first step required to use a language model. Given a string of characters c, a tokeniser converts it into a string of subwords 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 s have to be a good starting point for language modelling? If we knew this, then we could define an objective function with which we could evaluate tokenisers.

One line of prior work has adopted a causal definition of memorisation: it is the causal effect of observing an instance during training on a model's ability to correctly predict that instance (Feldman, 2020). Despite being an intuitive concept, quantification of this definition is not straightforward as it requires knowledge of a counterfactual: we must know how our model would have performed on a training instance had the model not been trained on it. To overcome this challenge, prior work has proposed a variety of methods to estimate memorisation. Some estimate it by training a model multiple times on different subsets of the data (e.g., Feldman and Zhang, 2020; Zheng and Jiang, 2022), while others implicitly assume this counterfactual's value to be negligible (Carlini et al., 2021). Both these approaches, however, have drawbacks: the first computes memorisation for an architecture rather than a specific model, while the second relies on a strong assumption (we discuss this in detail in §5).

Another open question is how to—given such an objective function—efficiently find a tokeniser which maximises it. Byte pair encoding (BPE; Gage, 1994; Sennrich et al., 2016), 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 logprobability. 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 first formalise counterfactual memorisation as the difference between two potential outcomes; notably, our formalisation generalises prior definitions of memorisation, allowing us to compare them within a unified framework. We then draw from the econometrics literature (Callaway and Sant'Anna, 2021) and propose a new method which estimates memorisation using only observational data; our method simply needs a model's performance measurements (e.g., loglikelihood) on a subset of the training data throughout training. The output of our method is what we term a memorisation profile: a model's memorisation of training batches over the course of training.

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. Given this objective, we then define the tokenisation problem as the task of finding a tokeniser which compresses a dataset to at most δ 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.

Empirically, we use this method to analyse memorisation for models in the Pythia suite (Biderman et al., 2023b) and characterise their memorisation profiles; e.g., Fig. 1 reports the memorisation profile of Pythia 6.9B. By studying these memorisation profiles we find that memorisation is stronger and more persistent in larger models. Furthermore, both the learning rate and the position of an instance in the training set considerably impact how strongly that instance is memorised. Finally, memorisation profiles are stable across model sizes; thus, we can predict memorisation in larger models from the memorisation observed in smaller ones.

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 problem. Practically speaking, our results imply that we are unlikely to discover an efficient algorithm for the problem of finding optimal tokenisers, and that we should focus on approximate algorithms (such as BPE or UnigramLM) instead.

Note that, even though in this paper we did not have any empirical results, this paragraph still focuses on concrete takeaways from our theoretical contributions.