WordPiece

We start where the previous page ended. A corpus is cut into words, every word is written out in single symbols, and a loop runs. Count every pair of adjacent symbols, weighting each by how often its word occurs, take the best pair, replace every occurrence of it with the two symbols written together, and go round again. Each turn adds one row to the vocabulary, so the loop stops when the vocabulary is the size that was asked for.

The teaching implementation keeps the same merge loop but changes the score used to select its next pair. It rewards pairs whose parts occur together more strongly relative to their individual counts.

We use the same held-out sentence and eighteen-sentence training corpus as the earlier examples. Later we compare a second, independent choice: longest-match encoding instead of replaying merges.

Dr. Alvarez didn't expect the low-cost re-analysis.

Take the eighteen sentences and count every adjacent pair once, before any merging. There are 87 pairs that occur at least twice, and the commonest of them is h followed by e, at 32 occurrences, which comes almost entirely from the word the. That looks like a discovery until you look at the two halves on their own.

The letter h occurs 36 times in the corpus and the letter e occurs 98 times, so nearly every h in the corpus is followed by an e, and the pair is frequent chiefly because e is everywhere.

Put every candidate on a chart, with how often it occurs across the bottom and, up the side, how often it occurs compared with what its halves alone would lead you to expect. If the two figures said the same thing the points would form a rising line and there would be nothing to argue about.

…

They do not. The commonest pair sits low, only the 32nd best of the 87 candidates by the other figure. The pair highest up the chart is o followed by f, which occurs three times and is the whole of the word of. Every o that starts a word in this corpus is one of six, every f that sits inside a word is one of three, and half of those o’s and all of those f’s are in the same three places. Counted on its own it has 45 of the 87 candidates ahead of it, which puts it in the lower half.

What a vocabulary row is worth is not how often its two halves happen to be adjacent, but whether those halves belong together, so that a model reading the joined piece learns something it could not get from the two separately. The test for belonging together is comparison against chance. If the two halves were sprinkled through the corpus independently of one another, how often would they land next to each other by accident, and how does that compare with how often they actually do?

Written out that way the fix is almost forced. We already have how often the pair occurs. We can get how often each half occurs anywhere, which is one more pass over the same counts. The comparison is a division.

Each candidate pair is scored by how often the two are adjacent, divided by the product of how often each of them occurs anywhere in the corpus. The pair with the largest such figure wins the turn.

score(a, b)  =  count(a, b) / ( count(a) × count(b) )

The denominator is the whole of the idea. Two halves that are each common make it large, so a pair of common symbols has to be extraordinarily frequent together to score well; two halves that are each rare make it small, so a pair of rare symbols needs only to be seen together a few times. A pair whose halves never appear apart from each other scores highest of all, because then the numerator and both parts of the denominator are counting the same occurrences.

log p(ab)  −  log p(a)  −  log p(b)

We need a corpus small enough to check by hand, so for the next three sections we drop to four words with their counts, the same four the previous page worked on. The word low occurs five times, lower twice, newest six times and widest three, sixteen occurrences in all, spelled in eleven distinct symbols. Eleven pairs of adjacent symbols exist across them, and here they are with both figures, orderable either way.

…

score(e, s) = 9 / (17 × 9) = 1/17 ≈ 0.0588
score(i, d) = 3 / (3 × 3) = 1/3 ≈ 0.3333

Ordered by the count, e followed by s is at the top and i followed by d is near the bottom. Ordered by the score they swap ends. That is not a small perturbation of one ordering into another; it is a different question producing a different answer on the same eleven rows.

Run both rules over the same spelling of the same corpus and put the results side by side. Each column is a full run, since every turn counts the corpus the turn before it left, so a disagreement at one step carries forward into every step after it.

…

On the four words the two part at the very first merge, counting taking e followed by s and the score taking i followed by d. On the eighteen sentences they part at the first merge too, counting taking h followed by e at 32 occurrences and the score taking o followed by f at three.

There is no corpus on this page where the two agree for even one turn, which is worth saying because a change of one word in the rule sounds like a refinement and here it produces a different vocabulary from the first row onwards.

Read the formula for what it favours and one sentence covers it. A pair of rare symbols that are only ever seen beside each other beats a pair of common symbols that are merely adjacent a great deal. On the four words that is i and d, which occur three times each and always together inside widest, beating e and s, which occur seventeen and nine times and are adjacent nine of those times.

What it will not buy is the row that a count-driven run buys first, which is the frequent pairing of two frequent symbols. On the eighteen sentences the count rule spends its first six turns assembling he, the, st, re, ed and The, every one of them a very common fragment of a very common word.

The score rule spends its first six turns on of, ex, exp, ly, Dr and Dr., of which of and Dr. are whole words of the corpus and ex and exp are the front of expect and expected. Those are recognisably different kinds of thing.

A vocabulary of pieces has to record where the spaces were, or the pieces cannot be glued back into a sentence. The previous page did that by marking the last symbol of each word, so that the w ending low is a different symbol from the w inside lower. WordPiece marks the other end. A piece that continues a word is written with two leading hashes and a piece that starts one is written plainly, so low is l, then ##o, then ##w.

A separate symbol standing for the space would be one more thing for the loop to merge, and it would merge with whatever sits beside it, so a piece could span the gap between two words before any word had been assembled. Marking a symbol instead keeps every merge inside one word by construction, since the words are counted separately and no pair ever spans two of them.

Given that, the choice is which end to mark, and both work. What has to be watched is that joining two marked symbols produces something sensible. Marking word starts, joining is always safe, since a word-initial symbol is only ever the left half of a merge and a mark at the far left of the left half stays at the far left of the result. Marking continuations, the arithmetic has to strip the mark from the right half at every join, or two hashes end up in the middle of a piece.

WordPiece also uses a different encoding rule: it searches the final vocabulary for the longest matching piece at the current position. BPE replays learned merges in order. This is a separate design choice from the score used to select pieces during training. A vocabulary alone does not specify how an input should be segmented.

Fitted on the eighteen sentences, here is the running sentence cut at four vocabulary sizes. Watch the marks rather than the pieces. Exactly one piece per word carries no mark, and it is always the first, so a reader can find the word boundaries by eye without knowing anything about the corpus.

…

At the largest size the sentence is 29 pieces for seven words. Two of the words come out whole, Dr. with its full stop and the word the, and low arrives as one piece with the hyphen after it marked as a continuation, which is the pre-tokenizer’s doing rather than the vocabulary’s, since nothing split low-cost into two words. The name Alvarez costs six pieces, which is the honest price of a word the corpus never held.

Now the part that is not cosmetic. Marking continuations means the first character of a word must have been seen starting some word of the corpus, and the rest must have been seen inside one. Marking ends means the last character must have been seen ending some word. Those are different requirements and the corpus satisfies them in different places, so the two spellings fail on different words.

…

Of the 35 characters the eighteen sentences use, thirteen never open a word and eighteen never end one. So Alvarez, which ends in a z and no word of the corpus ends in z, is spelled in six pieces by the continuation-marked vocabulary and defeats the end-marked one. The word zebra, which begins with a z and no word of the corpus begins with z, is exactly the other way round. The word you defeats both, since no word here starts with y or ends with u.

Something downstream will read these pieces, and it spends work per piece, so the length of a text in pieces is the currency everything is bought with. To price the scoring rule on its own we hold everything else fixed. The same corpus, the same spelling into symbols, the same number of merges, and only the choice of which pair to take at each turn differs.

…

The score-driven line is above the count-driven one at every budget on both corpora, which is what a rule that deliberately buys rare pairs must produce. On the eighteen sentences, ten merges take the corpus from 648 pieces to 504 under counting and to 614 under the score, and sixty merges reach 302 against 411. The count-driven run then runs out of pairs occurring twice after 84 merges, at 254 pieces, and the score-driven run needs 107 merges to reach 256.

The previous section held the spelling fixed to isolate the score. A reader choosing between the two schemes is not choosing a score, though, they are choosing a whole scheme, so here are complete fits of each at the same requested size, measured on the eighteen sentences and on the sentence kept out of them.

The middle of the table is the honest headline. At a vocabulary of 130 the count-scored scheme reads the corpus in 277 pieces and the sentence in 25, where this one needs 343 and 31, which is 24 per cent more on the corpus and six pieces more on seven words. The two columns cross only at the very end, where the count-scored fit has exhausted its pairs at 137 rows and this one keeps merging to 157, at which point the corpus figures are 254 against 263 and the sentence figures are still 29 against 25.

So why use it at all? Two things in that table point the other way, and one of them is not about length. The first is the crossing at the end. The count-scored run stops learning at 137 rows because nothing occurs twice any more, and 254 against 263 says that when both are allowed to finish, the score-driven one ends up marginally shorter on the corpus it was built from. It simply takes twenty more rows to get there.

The second thing that table does not show is what happened to the sentence. At every one of those sizes the continuation-marked fit reads it with nothing unspellable and gives it back exactly, and at every one of those sizes the end-marked fit leaves one piece of it unspellable and never gives the sentence back exactly, because of the z at the end of Alvarez. A shorter reading that has lost a character is not obviously the better reading.

One more consequence of cutting by longest match rather than by replaying merges. When the cut fails partway through a word, there is no sensible way to continue, since the pieces already chosen were chosen on the assumption that the rest would work out. So the whole word is thrown away and replaced by a single stand-in token.

Which of those is better is genuinely open. Handing on lo tells a model something, and it also tells it something false, since lo now appears in a context it never appears in. Handing on one stand-in tells the model only that a word was here, which is less information and no misinformation. What is not open is that the two are different, and a count of unspellable pieces means different things under the two schemes.

Go back to the very first merge on the four words. The pair i followed by d scores one third, and so does the pair w followed by i, and for the same reason, since i, d and the word-initial w each occur three times and each of those pairs occurs three times. The rule says take the largest score and there are two largest scores, so at this point the method has run out of instructions.

Any tie-break at all is added from outside. The choice made here is to compare the two candidates as text and take the smaller, which at least makes the answer independent of the order the corpus’s texts arrived in. Because the comparison happens in the spelling the merges are learned in, where a word’s first symbol carries a mark of its own, what actually decides is the position of that mark in the character table against the position of the letter i.

The mark is at 9601 and i is at 105, so i comes first, and the vocabulary contains ##id and does not contain wi.

A score computed from one occurrence is a fact about one word, so every implementation of this refuses to merge a pair seen fewer than some small number of times. There are two ways to read that rule and they are not the same rule. Either the minimum filters the candidates before the best is chosen, or it is a test applied to the winner, which ends the run when the winner fails it.

Under counting the two readings coincide, since the winner always has the largest count and a failing winner means every candidate fails. Under this score they come apart completely, because the winner can be a rare pair while common pairs are still unmerged. Set the minimum to three on the four words and measure both.

The second reading stops at five merges, on a candidate seen twice, and leaves ##est, ##ew, new, newest and widest unlearned although each of them comes from a pair occurring three times or more. So the rule that was meant to keep coincidences out of the vocabulary instead threw away most of the vocabulary, and it did so quietly, since the run reports itself finished. Filtering the candidates gets all ten.

The score is a division, and the first question to ask of any division is what happens as the denominator shrinks. Suppose two symbols occur only ever beside each other, which is the case the rule was built to reward. Then how often the pair occurs and how often each half occurs are all the same number, so the score is that number divided by its own square, which is one over the number.

score  =  c / ( c × c )  =  1 / c

That is not a large number, and worse, it falls as the pair gets commoner. Two symbols bound together nine times score one ninth; two symbols bound together twice score one half. So among pairs that are perfectly bound, the rule prefers the rarest, which is the reverse of what anybody wants from a vocabulary, and the division above is where that comes from rather than any choice an implementation made.

It is also worth saying what is not undefined here. Because the two halves are counted everywhere including inside the pair, the denominator can never reach zero, so the division is always safe. A version that counted only the halves’ free occurrences would divide by nothing at all for a perfectly bound pair, and would be undefined rather than infinitely good, which is a distinction worth keeping straight, since the second reading is the intuitive one and it is the one that breaks.

Section 4 derived the score as the likelihood gain one occurrence of a merge produces. The gain the whole corpus makes is that quantity multiplied by how many occurrences there are, and the rule does not do the multiplication. So the pair that raises the corpus likelihood most is not generally the pair this rule takes.

total gain  =  count(a, b) × log( N × score(a, b) )

On the four words, where the corpus is 79 symbols long, that total is largest for the pair s followed by t, at 19.55. The pair the score takes, i followed by d, gains 9.81, and the pair counting takes, e followed by s, gains 13.83. So neither rule takes the pair that most raises the quantity the score was derived from, and the pair that does is ranked fourth by the score and joint first by the count, losing that tie on alphabetical order.

Taking the longest piece at each position is greedy, and the worry that goes with any greedy rule is that it takes too much early and leaves a remainder it cannot finish, when some other division of the same word would have worked. It is worth being precise about when that can happen, because it is a fact about the vocabulary rather than about the cut.

Every merged continuation piece is built out of continuation symbols that are themselves in the vocabulary, so at any position after the first there is always a single-character piece available as a fallback. That means the cut can only fail after the first character if some character has no continuation form at all, and in that case no division of the word succeeds either. The greedy rule therefore refuses nothing that a search would have found.

All 1,578 of the later refusals are words containing an l or an n after the first character, and those two letters open words in this corpus without ever appearing inside one, so they have no continuation form. What each of those refusals reports is the missing symbol rather than a division the rule failed to find. Where a real vocabulary caps its alphabet and drops rare single characters, that guarantee is gone and the greedy failure becomes reachable, which is an argument for keeping the alphabet complete rather than for searching over divisions.

Changing what makes a pair worth merging does not change where the counts came from. The rows are a summary of one corpus, and whatever that corpus over-represented is cheap forever after, because the vocabulary is fixed before anything that reads it is trained.

Fitted to exhaustion on the eighteen sentences the vocabulary reaches 157 rows and reads its own corpus at 1.91 pieces per word, since analysis, expected and costing are all single rows and so is estimate with its full stop attached. A sentence in the same register but not in the corpus, “The dial was set and the diode tested.”, costs 2.38 pieces per word. The running sentence, which is about the same subject in the same language, costs 4.14.

Gathered in one place, these are the inputs on which the method is not approximate but undefined, together with what has to be decided in each case and what turns on the decision. Some are genuinely open, with defensible answers on both sides, and those are the ones worth attention, since they are decisions anybody implementing this has to make and nothing in the mathematics makes them.