Greed is All You Need: An Evaluation of Tokenizer Inference Methods (2024)

Abstract: While subword tokenizers such as BPE and WordPiece are typically used to build vocabularies for NLP models, the method of decoding text into a sequence of tokens from these vocabularies is often left unspecified, or ill-suited to the method in which they were constructed. We provide a controlled analysis of seven tokenizer inference methods across four different algorithms and three vocabulary sizes, performed on a novel intrinsic evaluation suite we curated for English, combining measures rooted in morphology, cognition, and information theory. We show that for the most commonly used tokenizers, greedy inference performs surprisingly well; and that SaGe, a recently-introduced contextually-informed tokenizer, outperforms all others on morphological alignment.

## introduction modern nlp systems, including large language models (llms), typically involve an initial step of mapping raw input text into sequences of subword tokens. these tokens are selected from a large vocabulary of candidates that were produced from algorithms such as byte-pair encoding (bpe; @xcite , wordpiece @xcite , or unigramlm @xcite . this process, which we refer to as the inference method of tokenization, is critical as it determines how all text is represented and subsequently modeled. each inference method offers distinct mappings, and we assert that it is not well-understood how these methods differ in performance. furthermore, popular implementation packages such as huggingface tokenizers, foot_0 sentencepiece, foot_1 and subwordnmt foot_2 often obfuscate or even restrict the choice of inference methods, making it unclear if inference-time decoding is compatible with the algorithm used to learn the tokenizer's vocabulary. moreover, it is yet to be determined whether such a match is ideal, or even necessary. in previous work regarding subword tokenization mostly concerns developing vocabulary construction algorithms @xcite @xcite @xcite , finding the optimal vocabulary size @xcite , building multilingual vocabularies @xcite , and using space positioning in the vocabulary tokens @xcite . others analyze the effects of vocabularies, finding intricate relations between algorithm or vocabulary and downstream performance @xcite , information theory @xcite , cognitive plausibility @xcite , impact on society @xcite , or morphological alignment @xcite @xcite @xcite . research concerning inference methods has been more scarce, and includes examination of random effects on bpe merges @xcite and application of sophisticated search algorithms @xcite . as far as we know, there exists no comprehensive study comparing inference methods across a variety of vocabularies and sizes using diverse metrics. in this work, we conduct a controlled experiment isolating the effects of inference methods over four tokenizers, introducing an evaluation suite aggregating intrinsic benchmarks from various theoretical realms. 4 we find that greedy inference methods work surprisingly well for all four vocabularies across morphological and information-theoretic metrics. furthermore, we demonstrate that sage yields state-of-the-art performance according to morphological metrics, and that inference methods that minimize token count perform strongest by cognitive metrics. ## inference methods let v denote a vocabulary of subword tokens and w denote a word (or 'pretoken'), the output of a pretokenizer. we define s(v, w) := (t 1 , ..., t k ) as a segmentation of w into k subword tokens such that ∀i, t @xmath0, ..., t k results in w. we use the term segmentation to denote the application of an inference method on a text given a token vocabulary, as well as its result. current widely-employed tokenization schedules couple together the tokenizer vocabulary with the inference method. however, we advocate for decoupling them, as they are independent pro-cesses. specifically, given a fixed token vocabulary produced from pre-training data, one could subsequently use any applicable inference method for the task at hand. thus, in our experiments, we use various intrinsic metrics to analyze the impact and performance of the several classes of inference methods: greedy inference methods only consider and produce one token at each step. we test three greedy approaches: longest prefix, which word-piece uses by default @xcite , selects the longest token in v that is a prefix of w, and then continues to iteratively segment the remaining text. longest suffix selects the longest token that is a suffix of w and continues iteratively @xcite . since this strategy diverges from english morphology, we consider it an intriguing baseline for assessing the impact of linguistic structure on the inference method. longest token selects the longest token that is contained in w, adds it to the generated segmentation, and then iteratively segments each remaining character sequence. this was proposed by @xcite to approximate words by their k longest tokens. they showed that it preserves morphological structure of words and leads to performance gains on some downstream tasks. merge rules-based inference methods begin with a word's character sequence and iteratively apply token-forming merge rules learnt by the tokenizer at the vocabulary creation phase, until none can be applied. this is bpe's default inference mode. 5 in our experiments we test two variants for bpe: the deterministic merge strategy recursively applies the first applicable bpe merge rule by its order in the trained merge list. dropout @xcite applies each valid merge rule with probability p, leading to a regularization effect where rare tokens surface more often and their embeddings can be better trained. it has been shown to improve machine translation performance. likelihood-based inference methods use individual likelihood values assigned to tokens in order to find a segmentation for w where the total likelihood is maximized @xcite . default uses likelihood values learned during vocabulary construction and considers the likelihood resource type size reference license ladec morphological 7,804 gagné et al. (2019) cc by-nc 4.0 deed morpholex morphological 12,029 sánchez-gutiérrez et al. (2018) cc by-nc-sa 4.0 deed morphynet morphological 219,410 batsuren et al. (2021) cc by-sa 3.0 deed dagobert morphological 279,443 hofmann et al. (2020) not specified-citation based unimorph morphological 143,454 batsuren et al. (2022) cc by 4.0 deed unblend morphological 312 pinter et al. (2020) gpl-3.0 compoundpiece morphological 22,896 minixhofer et al. (2023) not specified-citation based cognitive data cognitive 55,867 beinborn and pinter (2023) mit tokenization-scorer information theory -zouhar et al. (2023) not specified-citation based while not suggested so far as a standalone inference method, this obecjtive is proposed for both vocabulary training and inference in the pathpiece algorithm @xcite . ## intrinsic benchmark some analyses of tokenizers rely on training language models or translation models and evaluating their performance on downstream tasks. using this process to isolate effects of tokenization hyperparameters, such as inference method, is both time-and resource-consuming, as well as unstable due to the introduction of multiple sources of randomness throughout the lm/tm pre-training and fine-tuning phases. few measures have been introduced that are intrinsic to vocabularies and their direct application to corpora, and fewer still avoid conflating the measures with the objectives used in the vocabulary construction process itself. as a result, the body of work focused on improving tokenization schemes is still relatively small. we create and release a benchmark made to intrinsically evaluate subword tokenizers. we collected word-level datasets and information measures which have been shown, or hypothesized, to correlate with the performance of language models on various downstream tasks. details on these resources are provided in morphological alignment it is commonly assumed that, for a given tokenizer, alignment of word segments to morphological gold-standard segmentations is a predictor of the ability of a language model that uses the given tokenizer to represent words, especially 'complex' ones that are made up of several roots or contain multiple morphological affixes @xcite @xcite . we follow @xcite and evaluate our tokenizers's alignment with morphological annotations found in ladec @xcite , morpholex @xcite , mor-phynet @xcite , and dagobert (hofmann et al., 2020). we augment these datasets with morpheme segmentation data @xcite , novel blend structure detection data @xcite , and compound separation data @xcite . the number of words in each resource can be found in cognitive plausibility we use the benchmark and data from @xcite to measure the correlation of a tokenizer's output with the response time and accuracy of human participants in a lexical decision task, predicated on the hypothesis that a good tokenizer struggles with character sequences that humans find difficult, and vice versa. we report the average of the absolute value correlation scores across the four linguistic setups (word/nonword × accuracy/response time). tokens distribution statistics we report the rényi efficiency of different segmentations across a corpus @xcite . this measure penalizes token distributions dominated by either very high-and/or very low-frequency tokens, and was shown to correlate strongly with bleu scores for machine translation systems trained on the respective tokenizers. recent work @xcite 2024b) reveals a misalignment between rényi efficiency and downstream performance in certain cases, reinforcing the necessity of an evaluation suite grounded in diverse domains and disciplines, as advocated in this work. we also measure the average number of tokens per word over a corpus, as a proxy for compression quality @xcite . we omit the popular measure of character-length distribution of the tokens in the vocabulary, as it does not vary with segmentation strategy. lastly, we report the proportion of pretokens that are segmented different from the default across our reference corpus. ## experiments we evaluate inference methods for the following tokenizer vocabularies: bpe, unigramlm, word-piece and sage. we use the train split of the minipile @xcite dataset to construct the tokenizer vocabularies. we train vocabularies of sizes 32,768, 40,960, and 49,152, using the huggingface tokenizers library, with identical pre-tokenization, representing the text at byte level. unigramlm and sage require an initial vocabulary for their top-down algorithms; for the former, we used the default implementation of one million top n-grams, while sage was initialized with a 262k-size uni-gramlm vocabulary. this initial vocabulary also provided us with token likelihood scores for inference, although a more exact implementation would also incorporate the contextual sage objective. token distribution statistics measurements and decoding diff rates were computed over the test split of the minipile dataset. we measure the rényi efficiency using the tokenization-scorer package foot_5 with α = 2.5. for each tokenizer, all experiments ran within several minutes on a personal laptop computer, highlighting the usefulness of our benchmark as an efficient tool for in-loop hyperparamter tuning. we present the results on our benchmark for the 40k vocabularies in inference methods within each tokenizer, we find that the default ('intended') strategy is often outperformed by others on some measures. we observe a significant difference in morphological alignment when using merge rules-based inference methods. qualitative analysis showed the findings illustrated in inter-tokenizer results our results align with bostrom and durrett (2020)'s finding that bpe is inferior to unigramlm on morphology alignment. however, we show that some of this gap can be attributed not to the vocabulary but to the inference method. in addition, we find that sage is most aligned to morphology by a substantial margin, indicating that its contextualized objective succeeds in retaining meaningful tokens in the vocabulary during ablation. it is important to note that our evaluation is limited to english, a language with relatively low morphological complexity. previous studies have identified significant tokenization challenges in non-english languages @xcite . therefore, any definitive conclusions regarding the effectiveness of tokenization methods should ideally encompass a diverse array of languages. bpe and wordpiece, optimized for compression, unsurprisingly perform well above the likelihood-based vocabularies on the information measures. however, we note that this carries over to the cognitive benchmark as well, supporting beinborn and pinter (2023)'s findings. finally, we note that the two likelihood-based vocabularies follow the exact same within-vocab trends, and those for the two information-based vocabularies are also very close. this highlights the consistency and robustness of our benchmark, although some results are relatively close to each other, which can be expected considering that some inference methods do not change much of the token sequences (see rightmost column of ## conclusion in this work, we curated an aggregated benchmark for intrinsic evaluation of subword tokenizers and used it to show the importance of selecting an inference method suited for a vocabulary given a task. given its computational efficiency, we hope the benchmark can be used in lm training efforts as a fruitful first step to improve tokenization schemes, or to select inference methods on-line. concretely, our findings suggest that greedy inference is a good choice, especially for morphologically-motivated tasks, even for tokenizers trained on other objectives. considering its ease of implementation and faster inference, this is an encouraging finding. in the future, we plan to examine the correlation between our benchmark and various downstream tasks, as well as expand our experimentation to other languages and new algorithms.