Begone '##'! Converting continuation markers to word-initial markers

Under a very specific but nevertheless very common reading of the practice of “tokenization”, tokenizers are things that turn a string into sequences of atomic identifiers, i.e., integers. These identifiers are then sent to a downstream model, which uses them in some way. 1 Modern tokenizers are subword tokenizers. As the name implies, these tokenizers can segment text into pieces which are shorter than a word, which, in turn, makes them able to meaningfully segment words that would have been out of vocabulary for word-level tokenizers.

An example to illustrate the contrast: a word-level tokenizer can not show that “distinguish” and “indistinguishable” are related. Both words get unique and opaque IDs. Hence, if either one of these words has not been seen in training, then that word is just not usefully representable. 2 A subword tokenizer can work around this by representing words as sequences of (subword) tokens. For example, “distinguish” and “indistinguishable” can, respectively, be segmented into ["dis", "tinguish"] and ["in", "dis", "tinguish", "able"]. As you can see, some semblance of the word’s orthographic similarity is maintained in the segmentation. 3

Word-initial versus continuing prefixes

Tokenizers traditionally distinguish between word-initial subwords and continuing subwords. For example, if we imagine that “ingenuity” and “walking” both contain “ing” as a subword, the “ing” token would be different. How we mark this difference depends on the tokenizer: some tokenizers mark the initial word explicitly by inserting a space in front of it: the word-initial subword will become “ ing”. The continuing subword then becomes “ing”. Another paradigm is exactly the other way around: word-initial subwords become “ing”, and continuing subwords instead get prefixed with, e.g., “##”. From now on, I will refer to the former as “initial prefixed” while the latter will be called “continuing prefixed”. 4

Both approaches have their own set of issues.

Word-initial

One issue with word-initial prefixed subword tokens is that spaces need to be marked or inserted explicitly. For example, in the phrase “one dog”, a naïve application of word-initial tokenization will find the continuing version of “one”, not the correct initial version. This bug shows up in GPT-2, which does not insert a space at the beginning of the sequence (note that Ġ is the byte code for ` `):

from tokenizers import Tokenizer

tok = Tokenizer.from_pretrained("gpt2")
tok.encode("the dog the dog").tokens
['the', 'Ġdog', 'Ġthe', 'Ġdog']
tok.encode("the dog the dog").ids
[1169, 3290, 262, 3290]

As you can see, the first “the” in the sentence has a different ID. To fix this, you need to set the add_prefix_space attribute, which manually inserts a space in front of each pre-token. However, GPT-2 was apparently trained without inserting space prefixes. 5

Continuing

For continuing subword prefixes, the situation is a bit more dire. To reiterate: tokenizers with continuing subword prefixes explicitly mark whether a subword is word-initial or continuing. Therefore, these tokenizers insert orthographic markers that don’t really exist, e.g., the tokenizer will create "##ing", but ## was never part of the original string to begin with, it’s just a marker. You could also, for example, model this using an object like this:

from dataclasses import dataclass

@dataclass
class Token:
    form: str
    is_word_initial: bool

This, unfortunately, has the consequence of making vocabularies with continuing subword prefixes unusable with algorithms that don’t insert these markers. In practice, this means that it is not readily possible to transfer a BERT-like WordPiece vocabulary, to use the terminology in the Hugging Face libraries, to a BPE or UnigramLM model without changing the markers on the tokens from continuing subword markers to word-initial markers.

The opposite, however, is possible: BERT-like WordPiece models work well without continuing subword markers, which then begs the question why you would ever use continuation markers. The answer, as the following case study will show, is: you don’t!

Case study: left-to-right greedy inference

Now let’s turn to a simple example to drive the point home: left-to-right greedy inference. This is probably the simplest tokenization algorithm: given a vocabulary V and a string S, take the longest matching string in the vocabulary, slice this off of the beginning of the string. 6

def greedy_l2r(S: str, V: list[str]) -> list[str]:
    sorted_vocab = sorted(V, key=len, reverse=True)
    out = []
    while S:
        for item in sorted_vocab:
            if S.startswith(item):
                out.append(item)
                S = S[len(item):]
                break
        else:
            return ["[UNK]"]

    return out

Now, let’s consider a word-initial prefixed vocabulary:

greedy_l2r(" dogdoggo", [" dog", "do", "g", "o", "s", " cat", " clown"])
[' dog', 'do', 'g', 'g', 'o']

And now, the equivalent subword-prefixed vocabulary:

greedy_l2r("dogdoggo", ["dog", "##do", "##g", "##o", "##s", "cat", "clown"])
["[UNK]"]

This results in an [UNK] because our algorithm does not take into account the ## prefixes. So let’s amend it. 7

def greedy_l2r(S: str, V: list[str], continuing_subword_prefix: str = "##") -> list[str]:
    initial = [x for x in V if not x.startswith(continuing_subword_prefix)]
    continuing = [x.removeprefix(continuing_subword_prefix) for x in V if x.startswith(continuing_subword_prefix)]
    initial_vocab = sorted(initial, key=len, reverse=True)
    continuing_vocab = sorted(continuing, key=len, reverse=True)
    out = []
    while S:
        is_continuing = bool(out)
        if is_continuing: 
            selected_vocab = continuing_vocab
        else:
            selected_vocab = initial_vocab
        for item in selected_vocab:
            if S.startswith(item):
                out.append(f"{continuing_subword_prefix}{item}" if is_continuing else item)
                S = S[len(item):]
                break
        else:
            return ["[UNK]"]

    return out

As you can see, this algorithm requires us to create 2 separate lists, keep track of where we are in the string, and reinsert the marker after matching. When optimizing, this implies that we have to build 2 separate automata, while the word-initial tokenization scheme only requires one. So, even for greedy left-to-right inference, adding the continuing subword marker leads to more pain than gain.

Tokenizer normal form

Which brings me to the point I was working towards, which is that you should not use continuing subword markers. That’s the whole point! You can freely convert from continuing format to initial format by doing the following:

1. Add a word-initial marker to each token that does not have a marker
2. Remove all continuing markers
3. Make sure your algorithm does not expect continuing markers

If you know me, you also know what’s coming! skeletoken contains a helper to convert any tokenizer to word-initial without loss of information:

from skeletoken import TokenizerModel

model = TokenizerModel.from_pretrained("bert-base-uncased")
tok_regular = model.to_tokenizer()
tok_normal = model.to_normal_form().to_tokenizer()

a = tok_regular.encode("governmental preparedness supermajority").ids
b = tok_normal.encode("governmental preparedness supermajority").ids

assert a == b

print(tok_regular.encode("governmental preparedness supermajority").tokens)
['[CLS]', 'governmental', 'prepared', '##ness', 'super', '##ma', '##jo', '##rity', '[SEP]']
print(tok_normal.encode("governmental preparedness supermajority").tokens)
['[CLS]', ' governmental', ' prepared', 'ness', ' super', 'ma', 'jo', 'rity', '[SEP]']

Converting your tokenizer to normal form allows you to freely convert between inference formats, add and remove tokens safely, and keeps your downstream code free of checking for either initial markers or continuation markers, without any loss in quality.

Footnotes

1. This is a deliberate simplification: tokenization as a discipline is probably at least as old as NLP itself, and usually concerned itself with splitting up sequences of characters into sequences of words or morphemes. ↩
2. Traditionally, these tokens are just represented as [UNK]. ↩
3. This does not a priori mean that this similarity is useful, in fact, it might also be harmful. In general, orthographic similarity does not imply semantic relatedness. For example, you can imagine that not modeling subword similarity actually helps modeling the distinction between the pair “cat” -> “category”. ↩
4. I’m still not in love with this terminology. ↩
5. In my opinion, this is just a bug in how gpt-2 was trained. The add_prefix_space option should always be set to true if a tokenizer uses the space character as the initial prefix. ↩
6. Please, do not use this for anything serious, it’s a terrible implementation. Use an aho-corasick automaton. ↩
7. Please, don’t use this. ↩