Byte Pair Encoding

Every page in this section carries the same sentence, and this one carries a corpus beside it. The sentence is the one below, and I wrote the corpus myself, eighteen short sentences of ordinary English about reports and costs and analyses, chosen so that every character the sentence uses turns up somewhere in them and so that the words are plausible neighbours of the sentence’s own.

The corpus does not contain the sentence, and that is the whole arrangement we are going to study, since a vocabulary is only interesting on text it was not built from.

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

Cut on its spaces the sentence is seven words, and the corpus holds 72 distinct words across 133 occurrences. Five of the seven are absent from it, namely Alvarez, didn’t, expect, low-cost and re-analysis with its full stop attached. The corpus does have expected, and lower, and cost, and analysis, which is exactly the situation a real corpus is always in.

Suppose we make the vocabulary out of the words the corpus contains. That is 72 rows, and reading the sentence is then a lookup per word. Two of the seven are found, the and the abbreviation Dr. with its full stop. The other five are not, and there is nothing the vocabulary can do about them except hand back a single row meaning “something was here and I cannot say what”. Five sevenths of the sentence arrives at the model as that row, five times over, with nothing to tell the five apart.

Making the vocabulary larger does not fix this, it only moves the boundary. Whatever number we stop at, the words past it are mostly words the corpus saw once, and a table built from any corpus at all has a long tail of exactly that kind. A proper name is the clearest case, since there is no size of word table that contains the names.

The opposite choice has the opposite problem. Give the vocabulary one row per character and almost nothing is unspellable, since the sentence is made of characters and every character it uses does turn up somewhere in the corpus. The corpus uses 36 distinct characters, and the table comes to 51 rows rather than 36 because a character that ends a word is kept apart from the same character inside one, for a reason section 5 comes to.

Either way it is a very small table, and the sentence encodes to 45 pieces where a word vocabulary needed 7, while the corpus goes from 133 words to 648 pieces.

I wrote almost, and the qualification is not a hedge. One of those 45 pieces has no row in that table of 51, on a sentence every character of which the corpus contains, and the reason is the same distinction between 36 and 51 that the paragraph above passed over. Sections 11 and 12 are about it, and it is the most useful thing on this page.

Length is not a cosmetic cost. Whatever reads these pieces spends work per piece, and a model that has to look at 45 positions to see one sentence is spending most of its capacity learning that l followed by o followed by w spells a word it will meet a thousand times. It also has to carry information much further, since the beginning and the end of a thought are now six times as far apart as they were.

Byte pair encoding is the thing in between, and the way it gets there is worth stating before any detail. It does not decide what a piece ought to be. It starts at the character end, where almost nothing is unspellable, and then repeatedly buys one shorter sequence with one more row of the table, always buying whichever row shortens the corpus most. A frequent word is bought early and ends up as one piece; a rare one is never bought and stays as a few pieces that are themselves frequent.

So the vocabulary size stops being a choice between two regimes and becomes a dial. At the smallest setting we have the character vocabulary; turning it up trades rows for length, one row at a time, and every setting in between is available. On the corpus above, a fit that has made no merge at all reads the sentence in 46 pieces, and 85 merges later reads it in 26, while the corpus falls from 648 pieces to 263.

We need a corpus small enough to work by hand, so for the next four sections we drop to four words with their counts, which is the example Sennrich and colleagues worked in their own paper. The word low occurs five times, lower twice, newest six times and widest three, sixteen occurrences in all. Every word is written out as its characters, and the last character of each word carries a marker saying that a space follows it.

low  =  l  o  w</w>

The marker matters more than it looks. It makes the w that ends low a different symbol from the w inside lower, which is correct, since the two behave differently and a piece that ends words is a different thing from a piece that continues them. It also makes gluing the pieces back together a purely mechanical operation, because the spaces are recorded in the pieces rather than remembered separately. Counted this way the four words are spelled in 11 distinct symbols and the corpus is 79 pieces long.

Now count. For every word, look at each adjacent pair of symbols and add the word’s own count to that pair’s total, so a pair inside a word that occurs six times is worth six. Nothing else is counted, and in particular a pair that straddles two words is not a pair at all, because the words are held apart.

count(a, b)  =  Σ over words w   occurrences(w) × (times ab is adjacent inside w)

e + s:         6 + 3 = 9
s + marked t:  6 + 3 = 9
w + e:         2 + 6 = 8
l + o:         5 + 2 = 7

Take the pair with the largest count, replace every occurrence of it everywhere in the corpus with a single new symbol which is the two written together, and add that symbol to the vocabulary. Then count again on the respelled corpus and do it once more. That is the whole loop, and it stops when the vocabulary has reached the size we asked for, or earlier if no pair is left that occurs at least twice.

Notice what the count means once the merge is made. Joining a pair that occurs nine times removes nine pieces from the corpus, exactly, because each occurrence was two symbols and is now one. So the count is not a proxy for anything; it is the saving, in pieces, that the merge is about to make.

Run the loop ten times on the four words and the vocabulary assembles itself in front of us. Drag the control and watch the spellings shorten. The first merge joins e and s at 9; the second joins that new es to the marked t, also at 9, so after two steps the ending est with its marker is a single symbol shared by newest and widest.

By the seventh merge the whole word low with its marker is one piece, and by the tenth every one of the four words is a single piece.

…

This walk, and the twenty-two-row table it ends on, are the method exactly as Sennrich and colleagues published it, with nothing added underneath. That is deliberate, because it keeps the table small enough to read a row at a time; section 12 adds something underneath it and says what that costs.

Here is the part that is easy to miss. What the fit produced is not really a list of pieces, it is a list of merges with an order on them, and the order is load-bearing. To encode a new word, spell it in characters with the marker on the last one, then look for the earliest-learned merge that applies anywhere in it, apply it, and look again. Stop when no learned merge applies.

rank of a merge  =  its position in the order it was learned, and earlier is applied first

Reversing two merges gives a different tokenizer even though the set of pieces is the same, since a merge only applies to what the merges before it left behind. That is why a vocabulary cannot be shipped as a set of strings, and why two people holding the same rows will disagree about how to cut a word unless they also agree on the order.

Back to the eighteen sentences and the sentence they do not contain. Fitted to the point where the corpus has no adjacent pair left that it saw twice, the fit has learned 137 rows and the sentence comes out as 26 pieces. Every one of the five words the corpus never held is spelled, which is what the method was for, and the way they are spelled is worth looking at carefully.

…

Two of the cuts land where no linguist would have cut, and a third only looks as though it did. The hyphenated low-cost comes apart as lo, w, the hyphen on its own, and cost with its marker, so the first half is split between a piece that ends in the wrong place and a leftover letter.

The prefix in re-analysis does come out as re, which looks like morphology and is not, since re was merged at a count of 17 gathered from every word in the corpus holding those two letters, were and results among them. And analysis comes apart as analysi and then a final s carrying the full stop.

That last one had a reason I did not expect, and the six readings under the widget are what found it. The vocabulary does hold a row for analysis; handed the word on its own it answers one piece. But a row carries an end-of-word marker, and in the sentence the word ends in a full stop rather than in an s, so the row cannot apply and the fit falls back to the longest thing that can.

The same happens to cost, which is one piece alone and the last of four inside low-cost. The clearest case of it is expected against expect, where the corpus holds the longer word and not the shorter, so expected is one piece and its own stem is three.

Gluing the pieces back is mechanical. Concatenate them, then turn every marker into a space. Because the markers are inside the pieces, no separate record of where the spaces were is needed, and the round trip is exact on any text spelled entirely in symbols the corpus taught. That last clause is doing more work than it looks as though it is.

The sentence this method is usually sold with is that nothing it reads is ever out of vocabulary. That sentence is true of words and false of characters, which is worth separating out carefully, since the two cases behave nothing alike. A word the corpus never held is written out of smaller pieces and arrives intact, and that is the whole achievement of Part 1. A character the corpus never held has no smaller pieces to be written out of, so there is nothing for the same mechanism to do.

The reason is the loop rather than any choice made around it. A merge joins two symbols that already exist, so every row the fit ever adds is built from rows that were already there, and the rows that were already there are the alphabet the corpus arrived in. No vocabulary size can invent an alphabet row. Ask for a thousand and the alphabet is still whatever the corpus happened to contain.

Our own sentence falls into that hole, and I want to be exact about how, because it is narrower than the usual telling. The corpus does contain the letter z, in the word size. What it does not contain is any word ending in z, and since section 5 a letter that ends a word has been a different symbol from the same letter inside one.

So the symbol z-at-the-end-of-a-word was never in the alphabet, no merge could ever have produced it, and Alvarez ends in exactly that. The sentence uses no character the corpus lacks and is still not spellable.

Reading it under the method exactly as published, with nothing underneath the alphabet, the encoder hands back the stand-in row and the sentence comes to 25 pieces. Gluing them gives this, and the space is gone because a stand-in carries no marker and the marker was attached to the symbol it replaced.

Dr. Alvarez didn't   →   Dr. Alvare[UNK]didn't

Nothing was raised, and nothing about the fit was wrong; the size was met, the merges are the merges, and every number the fit reports about itself is correct. A text went in and a shorter, different text came out, with no signal anywhere that it had. That is the half of this worth dwelling on, because a refusal can be caught and handled and a silent substitution cannot, and the further a text sits from the corpus the more of it goes.

The Greek sentence in the next section reads as 22 pieces under the published method, 21 of them the same stand-in, and what comes back from gluing those is a run of stand-ins with a full stop on the end.

The repair is available because every character already has a spelling in something smaller than itself. Written out for storage, any character at all is a run of one to four bytes, and there are exactly 256 byte values whatever any corpus did. Give the table a row for each of those values, written so that it cannot be mistaken for a letter, and a character with no row of its own goes out as the rows of its bytes rather than as a stand-in.

This is usually called byte fallback, and it is what SentencePiece offers under that name.

the letter A   =   byte 65   =   the row <0x41>

It costs one more row than 256. A word whose last character had to be written in bytes still has to record that a word ended there, and the marker was attached to a character that no longer has a piece, so the marker gets a row of its own. It is 257 rows in all, and they are the same 257 rows whatever the corpus was, since nothing about them is learned.

…

On the running sentence the repair costs exactly one piece, 26 against 25, and the interesting part is that not one of the 26 is a byte row. The letter z has a row already; what it lacked was a row for z at the end of a word. So the fit writes the ordinary z and then the marker on its own, the space comes back, and the 256 byte rows are never reached at all. On this sentence the whole repair is the 257th row.

The other two texts are where the bytes do the work. The word café goes from four pieces, the last a stand-in with the accent gone for good, to six, the accented e written as the two byte rows for 195 and 169. The Greek sentence goes from 22 pieces that cannot be read back to 46 that can, 42 of the 46 being byte rows, so 25 characters arrive as 46 positions and whatever reads them has to work back up from bytes to letters nobody taught it.

A vocabulary fitted to Greek would do far better than that, which is the honest thing to say about it, and the alternative on offer here was the text not arriving.

Adding 257 rows raises a bookkeeping question, and the answer shows on the readouts, so it is worth saying rather than leaving to be discovered. The number we ask for bounds only what the corpus taught, which is the alphabet, the stand-in and the merges. The 257 sit underneath that and outside the budget, so asking for 54 gives a table of 311 rows and asking for 137 gives one of 394.

Counting them inside the budget instead is the other defensible answer, and it is the one SentencePiece takes. The price of it is a hard floor of 257 on every vocabulary, which would make the twenty-two-row table of section 8 impossible to ask for, and that table is the only reason section 8 can be read a row at a time.

The price of the choice made here is the one the table above shows, which is that the number asked for is not the width of the table, so a model sized from it alone would be 257 rows short.

The vocabulary size is the one number a person setting this up actually chooses, so it deserves a curve rather than a rule of thumb. Fit the eighteen sentences at fifteen different sizes and measure two things at each, what the whole corpus costs in pieces and what the one held-out sentence costs.

…

Both curves fall steeply at first and then flatten, which is the shape the counting guarantees. The first merge is worth the largest count in the corpus, the second the largest count in what is left, and so on downward, so each merge saves no more than the one before it. On this corpus the first merge joins h to the marked e and saves 31 pieces; the second joins t to the he-with-a-marker that first merge produced, saves 19, and gives the word the a row of its own.

It flattens completely at 137 rows here. Asking for 150, or 200, or 300 gives exactly 137, because the loop also stops when no adjacent pair is left that occurs at least twice, and a pair seen once is a fact about one word rather than about the language. So the size asked for is a ceiling and not a promise, and the number actually learned is a fact about the corpus.

There is a floor at the other end too, and it is also the corpus’s to set rather than ours. The smallest vocabulary that can exist is one row per symbol the corpus is spelled in plus one stand-in row, which is 52 here. Below that the request cannot be met at all, since dropping a symbol would leave part of the training corpus itself unspellable.

Between those bounds the size is a real trade, and it is worth naming both sides plainly. A larger vocabulary means shorter sequences, so whatever reads the pieces does less work per sentence and carries information a shorter distance. It also means more rows, and in a language model each row is an entire vector to learn, so the parameter count grows with the vocabulary while the number of times each new row is seen in training falls.

That second effect is the one that decides where to stop in practice. The rows a large vocabulary buys are, by construction, the ones that were merged last, which is to say the least frequent ones, so each of them is seen fewer times than every row before it. Past some point the sequence gets barely shorter while the table fills with rows the model has almost no evidence about, and on this corpus that point is visible in the table above, where going from 100 rows to 137 buys the sentence two pieces.

Section 12 gave a character alphabet a byte spelling to fall back on. The first variant goes further and makes bytes the alphabet outright. Every string, in any script, is some sequence of bytes when written out in the usual encoding, and there are exactly 256 byte values, so an alphabet of all 256 needs no corpus to fill it. Run the identical merging loop over byte sequences and there is no character alphabet anywhere in the fit, no stand-in row, and nothing underneath.

The two are easy to confuse and they are genuinely different. Under section 12 every merge is over characters and a byte appears only where a character has no row, so the merges know what a letter is. Here every merge is over bytes from the first step, so the early merges are spent reassembling the letters a character fit started with, and a merge is free to join the second half of one character to the first half of the next.

…

Both fits return all three texts exactly, so the widget is not a comparison of what survives. It is a comparison of length, and the ordering changes with the text. On the running sentence the byte fit is longer, 29 pieces against 26. On the accented sentence it is longer by one, 17 against 16. On the Greek sentence the two are exactly level at 46.

It is not free, and this is the place on the page where a variant is worse than the thing beside it. Fitted to the same eighteen sentences with the same number of merges, the byte alphabet reads the running sentence as 29 pieces where the character alphabet reads it as 26, and reads the corpus as 282 pieces where the character alphabet reads it as 263.

It is paying for two things, the byte values this corpus never uses, which are 220 of the 256 and which no merge can ever be spent on, and the spaces, which it carries as real symbols attached to the word that follows rather than as a marker.

Two things go the other way, and both are worth having. The byte fit’s table is the smaller of the two, 341 rows against 394, since it needs no character alphabet and no stand-in on top of its 256 and so pays for completeness once rather than twice. And on a single word with no space after it the byte fit is the shorter reading, since café is five pieces there against six, the sixth being the end-of-word marker a character fit has to emit on its own once the last character went out as bytes.

The second variant lifts the rule that has been in force since section 5, which is that a merge never joins two symbols belonging to different words. That rule was never argued for; it followed from counting the words separately. Lift it and a very common two-word sequence can become one row, which is worth two positions every time it occurs.

It cannot be lifted from the start, though, and the reason is the same greedy counting as everywhere else. With the boundary gone from the first merge, the commonest adjacent pairs in a corpus are things like the letter that ends one common word followed by the letter that starts the next, and the loop would spend its early merges on those and never build the words at all.

So the fit runs in two stages, ordinary merging within words up to a size stated in advance, then merging with the boundary ignored for whatever room is left.

stage one   merge within words, up to a stated size
stage two   merge over whole texts, up to the size asked for

Here the measurement was more interesting than the description. Run the second stage on our four-word corpus and it does not learn phrases at all, because that corpus has no phrases in it, only the same four words repeated. What it learns instead is a word doubled, newest followed by newest and low followed by low, which is a perfectly correct answer to the question it was asked and a useless vocabulary row.

…

Two things in that small run are worth naming. The second stage learned three merges and only two of them produced a row that spans a space, since the third joined an e to a marked r inside lower, which is the point about permitting rather than requiring. And a row spanning a space is not obliged to be two whole words.

On the eighteen sentences the stage does what the idea promises. Eight merges are learned after the lift and all eight produce a row spanning a space, six of them joining two complete words, of with the, and with the, report with was, rewrote with the, analysis with was, and the abbreviation Dr. with Bell.

A seventh joins costing to the row that already held and the, so it spans three words. The eighth is the one that makes the point about starting anywhere, since it joins the an that ends than to the following the, and an is not a word of these eighteen sentences at all.

The third variant goes the other way and forbids something. The complaint it answers is section 10’s, that the pieces are frequent substrings and have no opinion about where a prefix ends. Take a corpus of undo, untie, redo and retie, ten times each. Merging by count alone builds do and tie and un and re as symbols first, and then, since un followed by do is now as frequent as anything left, it joins them, and the row undo exists as a single piece with the prefix buried inside it.

The repair is not a rule added to the loop. It is a change to how the words are spelled before the loop starts. Cut each word at its joints and hand each part to the counter as if it were a word of its own, and then a pair straddling a joint is never adjacent, is never counted, and cannot be proposed. The loop is untouched.

…

It costs length, and on this corpus it costs a factor of two. Both fits were asked for thirty rows. The unconstrained one learns nine merges, ends at 19 rows, and reads the forty words of the corpus as 40 pieces, one per word. The constrained one learns the same first five merges and then stops, at 15 rows, because every part is by then a single symbol and every pair that remains straddles a joint. It reads the same forty words as 80 pieces, two per word.

What is bought for that doubling is that the un in undo is the same row as the un in untie, and the do in undo the same row as the do in redo, so a model reading these pieces can see the shared structure that the unconstrained vocabulary merged away. Whether that is worth twice the sequence length is not something this corpus can settle, and I have not measured it against a model here.

Go back to the very first merge on the four words. The pair e followed by s scores 9, and so does the pair s followed by the marked t. The rule says take the largest count and there are two largest counts, so at this point the method has run out of instructions. Any tie-break at all is something added from outside, and the usual choice is whichever pair the implementation happened to meet first, which makes the answer depend on the order the texts arrived in.

…

What the two branches actually do is worth measuring rather than asserting, because the usual claim is that a tie changes everything downstream. Here it does not. Taking either branch and finishing the fit leaves the corpus at 22 pieces, and nine of the ten rows are identical; the branches differ in one row, es on one side against st with its marker on the other, and the word lowest comes out as the same three pieces either way.

The second tie, three pairs at 6 four merges later, is the interesting one, since all three branches again leave the corpus at 22 pieces and one of them cuts lowest as two pieces rather than three.

Section 7 noted that taking the largest count is the biggest saving available now, and that this is not the same as the biggest saving available over a run. The method is a greedy one, and greedy methods are not generally optimal. Here that is not a worry to be waved at, since on a corpus small enough we can enumerate every sequence of merges and know the answer.

Take three words, report twice, taste eight times and state ten times, which is 102 pieces spelled in characters. Three pairs tie for first place at 18, s followed by t, t followed by a, and t followed by the marked e, and every one of them saves the same 18. Take any of them and one merge leaves the corpus at 84.

But the branches part immediately afterwards, and the branch beginning with t followed by a is two merges from a corpus of 66 while the branch beginning with s followed by t cannot do better than 74.

after s + t:   best pair left scores 10,   84 − 10 = 74
after t + a:   t + marked e scores 8 + 10 = 18,   84 − 18 = 66

Eight pieces on a corpus of 102 is about eight per cent, held steady out to four merges, and the loss is locked in by the first move. So the method is a heuristic for shortening a corpus and not a solution to it, and the two failures compound, since the first move here was a tie and the tie-break chose the losing branch. Nothing in the counting could have seen that coming, because at the moment of choosing, the three candidates were worth exactly the same.

The merges are a summary of one corpus and of nothing else. That is the source of the method’s power, since it is how frequent things become cheap without anybody deciding which things are frequent, and it is also permanent in a way that is easy to underestimate. Whatever that corpus over-represented is now cheap forever, and whatever it under-represented is now expensive forever, and neither can be argued with later, because the vocabulary is fixed before the model that reads it is trained.

On our eighteen sentences the row for expected exists and the row for expect does not, because those sentences use the past tense and never the bare stem. Nothing is wrong with that fit; it is the right answer for that corpus. But every text this vocabulary ever reads will be cut that way, so a text written mostly in the present tense pays three pieces for a word this one pays one for, and no amount of evidence afterwards can move the row.

Which is why what happens on the way down matters more than which rows a vocabulary holds. A piece the merges never built cannot be reached at all, so the word is written out of smaller pieces instead, and how small those get is what decides whether a text is readable or merely present. A text from a different domain backs off to short pieces and gets somewhat longer, the way expect goes from one piece to three here.

A text in a script the corpus never contained backs off all the way to bytes, and the Greek sentence of section 12 arrives as 46 pieces for 25 characters, which is worse than the character vocabulary Part 1 rejected. In every one of those cases the vocabulary was doing exactly what it was fitted to do.

Gathered in one place, these are the inputs on which the method stops being defined rather than becoming approximate, together with what has to be decided in each case and what turns on the decision. Several of them are genuinely open questions with defensible answers on either side, and those are the ones worth a reader’s attention, since they are the decisions anybody setting this up has to make and nothing in the mathematics makes for them.