WordPiece › The Greedy Tokenization Algorithm

Once training is complete, tokenizing new text with WordPiece uses a different strategy than BPE. BPE applies its learned merge rules sequentially in the order they were learned. WordPiece uses a greedy longest-match-first approach instead.

For each word in the input, the algorithm attempts to find the longest prefix of the word that exists in the vocabulary. It takes that prefix as the first token, then repeats for the remaining suffix. The suffix tokens receive the ## prefix. If at any point no prefix at all exists in the vocabulary (not even the single-character fallback), the entire word becomes [UNK].

Think of this as a greedy left-to-right scan through the word, always grabbing the biggest bite the vocabulary allows at each step. The algorithm never backtracks: once it has committed to a prefix, it continues from that point. This greedy nature means it can occasionally produce suboptimal segmentations for ambiguous cases, but those cases are rare in practice because the vocabulary is designed to give good coverage.

The procedure for tokenizing a single word is:

1. Start at the beginning of the word
2. Find the longest prefix that is in the vocabulary
3. Emit that prefix as a token
4. If there is remaining text, prepend ## to it and go back to step 2
5. If at any point no prefix (not even the first character) is in the vocabulary, replace the entire word with [UNK]

This greedy algorithm is fast and deterministic: it always produces the same segmentation for a given word and vocabulary. Unlike BPE, which requires storing and re-applying ordered merge rules, WordPiece inference requires only a lookup in the vocabulary dictionary, which makes it slightly simpler to implement and slightly less sensitive to the order of training merges. There is no list of merge rules to store: the vocabulary itself encodes all the information needed to tokenize, because the greedy algorithm implicitly reconstructs the appropriate segmentation.

This difference in inference approach is worth emphasizing. BPE tokenization is inherently rule-based: you apply rule 1, then rule 2, then rule 3, in the order they were created. The order matters because later rules were designed assuming earlier ones have already been applied. WordPiece inference has no such ordering dependency: you simply look up the longest matching prefix at each position. The vocabulary was built by learning which merges were informative, but the tokenization itself just does dictionary lookups. This makes WordPiece tokenizers easier to serialize, share, and apply in different computational environments.

Let us trace through tokenizing the word "unplayed" using a small WordPiece vocabulary that contains: un, ##play, ##ed, play, ##ing, a, and individual characters including u, ##n, ##p, ##l, ##a, ##y, ##e, ##d.

Starting at the beginning of "unplayed":

1. Try "unplayed" as a whole: not in vocabulary.
2. Try "unplaye": not in vocabulary.
3. Try "unplay": not in vocabulary.
4. Try "unpla": not in vocabulary.
5. Try "unpl": not in vocabulary.
6. Try "unp": not in vocabulary.
7. Try "un": found in vocabulary. Emit un. Remaining: "played".
8. Prepend ## to remaining: "##played".
9. Try "##played": not in vocabulary.
10. Try "##playe": not in vocabulary.
11. Try "##play": found in vocabulary. Emit ##play. Remaining: "ed".
12. Prepend ## to remaining: "##ed".
13. Try "##ed": found in vocabulary. Emit ##ed.

Final tokenization: un, ##play, ##ed.

This greedy search always finds the longest matching prefix at each step. If a character has no match at all (not even as a single character in the vocabulary), the entire word becomes [UNK]. In practice, BERT's vocabulary includes all Unicode characters it encountered during training, so single-character fallbacks are almost always available.

Notice how the algorithm naturally decomposes the word into morphologically meaningful parts: the prefix un-, the root play, and the past tense suffix -ed. This is not coincidental. The WordPiece training procedure, by using PMI-based scoring, tends to merge characters into units that are linguistically meaningful, because such units have strong statistical dependencies. The greedy tokenization then recovers these units efficiently.

Let us trace a second example to see the [UNK] fallback in action. Suppose our vocabulary does not contain the character ##z (because the training corpus contained no words with z after the first character position). If we try to tokenize "puzzling", we would proceed:

1. Try "puzzling": not in vocabulary.
2. Try longer and shorter prefixes until we reach "p": found in vocabulary. Emit p. Remaining: "uzzling".
3. Prepend ##: "##uzzling".
4. No prefix starting with ##u exists (suppose ##u is not in the vocabulary either).
5. The algorithm returns [UNK] for the entire word.

This shows that the [UNK] fallback is triggered by the inability to make any forward progress, not just by failing to match the whole word. The entire word is replaced with [UNK] as a conservative choice. For BERT's actual 30,000-token vocabulary, this almost never happens because the vocabulary covers a wide range of characters.